# Sharing two clean C++ solutions: iterative with stack (13ms) and recursive (16ms)

• Iterative approach:

Basic idea is to keep a stack of expressions, each expression contains left operand and operator. And we keep a "num" as our right operand.

If we meet a "(" we push stack.
If we meet a ")" we compute and pop stack, assign computed value to num.
If we meet a "+" or "-" we need to compute top of the stack and update the operand.
After we are done with the string, we need to check if there's a right operand remaining, if yes, we compute the last one.

``````    struct Expr {
int left;
int op;
Expr() : left(0), op(1) {}
int compute(int right) {
left = left + op * right;
return left;
}
};
int calculate(string s) {
/* using stack */
vector<Expr> history;
history.push_back(Expr());
int num = 0;
bool hasNum = false;
for (int i=0; i<s.size(); i++) {
char c = s[i];
if (c == ' ') continue;
if (c == '(') {
history.push_back(Expr());
} else if (c == ')') {
num = history.back().compute(num);
history.pop_back();
} else if (c == '+' || c == '-') {
int value = history.back().compute(num);
history.back().op = c == '+' ? 1 : -1;
num = 0;
hasNum = false;
} else {
num = num * 10 + c - '0';
hasNum = true;
}
}

if (hasNum) num = history.back().compute(num);
return num;
}
``````

The recursive approach:
If we meet a "(" we call recursion and when we meet a ")" we return computed value and next position to upper level.
At each level, if there's no "(" and ")" we compute like we do in the iterative approach.

``````    int calculate(string s) {
int nextPos = 0;
return calculateSub(s, 0, nextPos);
}

int calculateSub(const string& s, int pos, int& nextPos) {
int sum = 0;
int num = 0;
int sign = 1;
for (int i=pos; i<s.size(); i++) {
if (s[i] == ' ') {
continue;
} else if (s[i] == '(') {
int nextPos = i+1;
sum += sign * calculateSub(s, i+1, nextPos);
i = nextPos;
} else if (s[i] == ')') {
sum += sign * num;
nextPos = i;
return sum;
} else if (isNum(s[i])) {
num = num * 10 + s[i] - '0';
} else {
sum += sign * num;
num = 0;
sign = s[i] == '+' ? 1 : -1;
}
}

sum += sign * num;

return sum;
}

inline bool isNum(char c) {
return c <= '9' && c >= '0';
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.