LeetCode 227. Basic Calculator II

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.

解析：实现一个简单的计算器功能，操作包括+、-、*、/运算。

思路：这里涉及到运算优先级的问题，挨个遍历字符，如果只是数字则进行数值累加，如果是运算符，则分别针对加减和乘除进行处理。如果是加减，则将数值入栈；如果是乘除则将当前元素和栈顶元素进行运算，然后将结果入栈。这样栈中存放的都是加减的运算结果，最后将栈中所有元素进行求和返回最终结果。具体代码如下：

class Solution {
public:
    int calculate(string s) {
        int result = 0;
        stack<int> st_nums;
        if (s.empty())
            return result;
        int n = s.size();
        int num = 0;
        char op = '+';
        for(int i=0; i < n; i++)
        {
            if(s[i] >= '0')
            {
                num = num *10 + (s[i] -'0');
            }
            if(s[i] < '0' && s[i] != ' ' || i==n-1 )
            {
                if(op=='+')
                    st_nums.push(num);
                else if(op=='-')
                    st_nums.push(-num);
                else if(op =='*' || op =='/')
                {
                    int temp = (op=='*')? st_nums.top()*num:st_nums.top()/num;
                    st_nums.pop();
                    st_nums.push(temp);
                }
                op = s[i];
                num = 0;
            }
        }
        while(!st_nums.empty())
        {
            result += st_nums.top();
            st_nums.pop();
        }
        return result;
    }
};