[Algorithm] Basic Calculator

Basic Calculator:

Problem Statement

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Solution 1: Iterative Approach

Let's first examine the iterative way of solving this problem. Typically, we need to involve a scope stack which is quite a common technique in iterative approach. The rule is simple, we define scope as sub-expression surrounded by "(" and ")". Whenever we meet a "(" we push the scope, whenever we meet a ")" we pop the scope.

And inside each sub-expression we follow the post operation rule, meaning that we can view the expression as post polish notation, namely "x + y" is "x y +". We don't need to literally change it to post notation, we can evaluate expression in that fashion. What do I mean by saying this, this means:

1) If we are looking at an operator: Calculate the previous pending operation and save the current operator as pending operator, the left operand is the previous operation's result.

2) If we are at the end of sub-expression: Calculate the previous pending operation and we have the final result.

The pending operation is modeled as left operand and operator, and we keep right operand on the side as we go along the expression.

When we meet a ")" we are done with this scope, we compute the pending operation and save the current result as right operand, pop the scope and move on.

Keep in mind:

1) We use a scope stack to manage sub-expression defined by "(" and ")".

2) We keep the left operand and operator only, we always calculate to maintain this.

3) Right operand can be number we read from string or number carried from i+1 scope to i scope

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

class Solution { struct Node { Node() : value(0), op('+') {}; inline void calculate(long long v) { value = (op == '+') ? value + v : value - v; } long long value; char op; }; public: int calculate(string s) { vector<Node> stack; if (s.empty()) return 0; stack.push_back(Node()); long long rightOperand = 0; bool hasNum = false; for (int i=0; i<s.size(); i++) { if (s[i] == ' ') continue; if (s[i] == '(') { stack.push_back(Node()); continue; } if (s[i] == ')') { if (hasNum) stack.back().calculate(rightOperand); rightOperand = stack.back().value; hasNum = true; stack.pop_back(); continue; } /* when meeting an operator compute the previous value */ if (s[i] == '+' || s[i] == '-') { stack.back().calculate(rightOperand); stack.back().op = s[i]; rightOperand = 0; hasNum = false; continue; } hasNum = true; rightOperand *= 10; rightOperand += (s[i] - '0'); } if (hasNum) { stack.back().calculate(rightOperand); } return stack.back().value; } };

Solution 2: Recursive Approach

Recursive approach is kind of similar except that it uses program stack as its scope stack. When we meet a "(" we call recursion, evaluate the sub-expression and return back when we have met an ")".

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

class Solution { public: int calculate(string s) { int next = 1; return helper(s, 0, s.size(), next); } inline int helper(const string& str, int s, int n, int& next) { int sum = 0; int op = 1; for (int i=s; i<n; i++) { if (str[i] == ' ') { continue; } if (str[i] == '+' || str[i] == '-') { op = (str[i] == '+') ? 1 : -1; continue; } if (str[i] == '(') { sum += op * helper(str, i+1, n, i); continue; } if (str[i] == ')') { next = i; return sum; } int j = 0; int num = 0; while(isdigit(str[i+j])) { num *= 10; num += str[i+j] - '0'; j++; } i = i+j-1; sum += op * num; } return sum; } };