[LeetCode]227. Basic Calculator II

Problem

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

Analysis

数值计算.题目说明,字符串中包括0-9数字,+,-,*,/,以及空格’ ‘, 不包含字母以及括号. 一种方法,可以将字符串转换成逆波兰表达式,然后再计算. 另一种方法是使用栈,直接计算.但是这里还设计到运算符优先级的问题.

这里使用一个栈结构,存入数字,同时,把”+”和”-“纳入数字中,”-“,相当于加上”-num”; 同时注意,数字并不一定是0-9范围内,可能是2位数或更高; 另外, 需要确定什么时候对数字进行计算. 设计到优先级的问题. 比较上一个运算符和当前运算符之间的优先级,如果上一个运算符是”+”或者”-“, 将这个数字(两个运算符之间的数字,也就是上一个运算符针对的这个数字), 然后更新运算符; 如果上一个运算符是”*”或者”/“, 需要从数字栈中弹出一个数字,和当前数字,根据上一个运算进行运算,然后把运算结果压入数据栈, 更新运算符.

最后数据栈中,对应的运算都是+加法运算,依次弹出,直到数据栈为空,返回计算结果.

Code

class Solution {
public:
    int calculate(string s) {
        long result = 0, num = 0, n = s.size();
        stack<int> data;
        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 == '+') data.push(num);
                else if (op == '-') data.push(-num);
                else if (op == '*' || op == '/'){
                    int temp = (op == '*' ? data.top()*num : data.top()/num);
                    data.pop();
                    data.push(temp);
                }
                op = s[i];
                num = 0;
            }
        }
        
        while (!data.empty()){
            result += data.top();
            data.pop();
        }
        return result;
    }
};

References

https://www.cnblogs.com/grandyang/p/4601208.html