Problem description:

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: “3+2*2”
Output: 7
Example 2:

Input: “ 3/2 “
Output: 1
Example 3:

Input: “ 3+5 / 2 “
Output: 5
Note:

You may assume that the given expression is always valid.
Do not use the eval built-in library function.

Solution:

The idea is to use stack to store every signed numbers in it. One thing to notice is that we need to use a variable to denote positive of first digit. Whenever we reach to second operator, we can definitely push the previous result into stack. For example:

-1+2 : the sign was initially -. When we meet second operator +, we can push -1 into the stack. then set sign to +

Therefore, we need a stack to store calculated value. sign to store a sign that waited to be calculated. tmp is current value.

Example: 3+5/2

1
2
3
4
5
6
7
       init-> 0 -> 1  -> 2 -> 3   -> 4(reach to end)
stack:  []->  []-> [3]->[3]->[3,5]->[3,5] become [3,2] after calculation
sign:   + ->  + -> +  -> + -> /   -> 2
tmp:    0 ->  3 -> 0  -> 5 -> 0   -> 0

Then, just add up value in stack.
3+2 = 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# when we reach to second operator, calculate result and push to stack
        if not s:
            return 0
        # might have multiple digits number
        num = 0
        stk = []
        sign = '+'
        for i in range(len(s)):
            if s[i].isdigit():
                num = num*10 + int(s[i])
            if s[i] in '+-*/' or i == len(s)-1:
                if sign == '+': # sign is the previously not yet calculated sign
                    stk.append(num)
                if sign == '-':
                    stk.append(-num)
                if sign == '*':
                    num *= stk.pop()
                    stk.append(num)
                if sign == '/':
                    num = int(stk.pop()/num)
                    stk.append(num)
                sign = s[i]
                num = 0
        return sum(stk)
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
class Solution {
public:
    int calculate(string s) {
        stack<int> stk;
        char sign= '+';
        int res= 0, tmp= 0;
        for(int i= 0; i< s.length(); i++){
            if(isdigit(s[i]))
                tmp= 10*tmp+s[i]-'0';
            if(!isdigit(s[i]) && !isspace(s[i]) || i == s.length()-1){
                if(sign == '-')
                    stk.push(-tmp);
                else if(sign == '+')
                    stk.push(tmp);
                else{
                    int num;
                    if(sign == '*')
                        num= stk.top()*tmp;
                    else
                        num= stk.top()/tmp;
                    stk.pop();
                    stk.push(num);
                }
                sign= s[i];
                tmp= 0;
            }
        }
        while(!stk.empty()){
            res+= stk.top();
            stk.pop();
        }
        return res;
    }
};

time complexity: O(n)
space complexity: O(n)

reference:
http://www.cnblogs.com/grandyang/p/4601208.html