题目描述

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

样例

输入: " 3+5 / 2 "
输出: 5

算法1

(表达式求值) $O(n)$

两个栈：操作数栈，运算符栈
* 遇到空格，跳过
* 遇到数字，计算出完整的数字压入操作数栈中
* 遇到加减乘除运算符，需要考虑优先级
    1.如果遇到的操作符的优先级小于等于栈顶操作符的话，如A*B+C或者A*B*C，则直接计算
    2.如果遇到的操作符的优先级大于栈顶操作符的话，如A+B*C，把当前运算符压入栈中。
* 计算：操作数栈弹出两个值，运算符栈弹出一个值进行运算，把结果压入栈中

Java 代码

class Solution {
    public int calculate(String s) {
        Stack<Integer> num = new Stack<>();
        Stack<Character> op = new Stack<>();
        Map<Character,Integer> pr = new HashMap<>();
        pr.put('+',1);
        pr.put('-',1);
        pr.put('*',2);
        pr.put('/',2);
        char[] c = s.toCharArray();
        for(int i = 0; i < c.length; i++){
            if(c[i] == ' ') continue;
            else if(Character.isDigit(c[i])){
                int x = 0, j = i;
                while(j < c.length && Character.isDigit(c[j])){
                    x = x * 10 + c[j++] - '0';
                }
                i = j-1;
                num.push(x);
            }else{
                while(op.size() != 0 && pr.get(c[i]) <= pr.get(op.peek())) eval(num,op);
                op.push(c[i]);
            }
        }
        while(op.size() != 0) eval(num,op);
        return num.peek();
    }

    void eval(Stack<Integer> num, Stack<Character> op){
        int b = num.pop();
        int a = num.pop();
        char c = op.pop();
        if(c == '+') a += b;
        else if (c == '-') a -= b;
        else if (c == '*') a *= b;
        else a /= b;
        num.push(a);
    }
}