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.

You may assume that the given expression is always valid.

Some examples:



Note: Do not use the eval built-in library function.

Credits:

Special thanks to @ts for adding this problem and creating all test cases.

和Basic Calculator比較相似。都是很巧妙的解法。

runtime:24ms

class Solution {

public:

    int calculate(string s) {

    int len=s.size();

    if(s.empty())

        return 0;

    stack<int> st;

    int num = 0;

    char sign = '+';

    for(int i=0;i<len;i++){

        if(isdigit(s[i])){

            num = num*10+s[i]-'0';

        }

        if(!isdigit(s[i]) &&' '!=s[i] || i==len-1){

            if(sign=='-'){

                st.push(-num);

            }

            if(sign=='+'){

                st.push(num);

            }

            if(sign=='*'){

                int tmp=st.top();

                st.pop();

                st.push(tmp*num);

            }

            if(sign=='/'){

                int tmp=st.top();

                st.pop();

                st.push(tmp/num);

            }

            sign = s[i];

            num = 0;

        }

    }

    int re = 0;

    while(!st.empty()){

        re += st.top();

        st.pop();

    }

    return re;

    }

};