表达式求值

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

• 数据保证给定的表达式合法。
• 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 231−1231−1。
• 题目中的整除是指向 00 取整，也就是说对于大于 00 的结果向下取整，例如 5/3=15/3=1，对于小于 00 的结果向上取整，例如 5/(1−4)=−15/(1−4)=−1。
• C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 105105。

输入样例：

(2+2)*(1+1)

输出样例：

8

求解思路

关键点：设置两个栈：操作数栈和运算符栈。

之后通过4种情况进行判断：

（1）如果是操作数的话：将数加入到操作数栈种。

（2）如果是（：直接加入到运算符栈种。

（3）如果是 ）: 将进行计算，直到遇见左括号，就是相当于计算括号中的值。（具体来说就是运算数栈出栈两个数，运算符栈出栈一个运算符，将运算结果入运算数栈。最后将左括号出栈）

（4）如果是运算符：判断运算符的优先级，分以下两种情况

• 如果运算符栈顶的优先级大于该运算符，则进行出栈计算，新值入栈，直到运算符栈为空或者优先级大于运算符栈的栈顶元素

• 否则，新运算符直接入栈。

代码为：

import java.util.*;
import java.io.*;
public class Main{
    static Stack<Integer> num = new Stack<>();
    static Stack<Character> op = new Stack<>();
    //计算
    public static int eval(){
        int a = num.pop();
        int b = num.pop();
        char o = op.pop();
        int res = 0;
        if (o=='+') res = b+a;
        if (o=='-') res = b-a;
        if (o=='*') res = b*a;
        if (o=='/') res = b/a;
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int len = s.length();
        Map<Character,Integer> map = new HashMap<>();
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        map.put('/',2);

        for (int i = 0;i<len;i++){
            char a = s.charAt(i);
            int x = 0,j = i;
            if (Character.isDigit(a)) {
                //因为a取的是一位字符，指的是一位整数，下面这个循环是解决，两位数或多位数的情况：43/567.。
                while (j < len && Character.isDigit(s.charAt(j))) x = x * 10 + s.charAt(j++) - '0';
                //将x加入数值栈中
                num.push(x);
                i = j - 1;
            }
            //左括号没有优先级，直接入栈
            else if (s.charAt(i)=='(') op.push(s.charAt(i));
            //遇到有括号，计算括号里面的数值，也就是遇到左括号时结束。
            else if (s.charAt(i)==')') {
                while (op.peek()!='(') {
                    int eval = eval();
                    num.push(eval);
                }
                op.pop();
            }
            //判断入栈运算符的优先级
            else {
                while (op.size()!=0 && op.peek()!='(' && map.get(op.peek())>=map.get(s.charAt(i))) {
                    int e = eval();
                    num.push(e);
                }
                op.push(s.charAt(i));
            }
        }
        while (op.size()>0) {
            int e = eval();
            num.push(e);
        }
        System.out.println(num.peek());
    }
}