题目：
给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。
注意：
数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-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()函数中的整除也是向下取整，在本题中不能直接使用。
样例：
输入： (2+2)*(1+1)输出： 8
思路：
此题考虑用栈，为中序遍历，有两个关键点
双栈，一个数字栈存取数字，一个运算符栈存取所有运算符
那么如何入栈呢？
数字直接入栈
括号优先级最高，遇到左括号直接入栈
遇到右括号代表括号结束，则进行运算操作，进行几次运算呢？ 直到运算符栈的栈顶是左括号，具体来说就是数字栈出栈两个数，运算符栈出栈一个运算符，将运算结果入运算符栈。
如果是运算符
如果运算符栈为空，直接入栈
如果该运算符优先级大于运算符栈顶优先级，那么入栈
如果优先级小于等于运算符栈栈顶元素，则进行运算操作。直到运算符栈为空或者优先级大于运算符栈的栈顶元素
这个方法的时间复杂度为O(n)，整个字符串只需要扫描一遍。
如果对栈的操作不熟悉，可以看看我的这篇文章
https://blog.csdn.net/m0_68055637/article/details/128593504?spm=1001.2014.3001.5502
代码：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Stack; public class Main { static Stack<Integer> nums=new Stack<>(); //数字栈 static Stack<Character> ops=new Stack<>(); //运算符栈 public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); HashMap<Character,Integer> map=new HashMap<>(); //存放运算符优先级 map.put('+',1); map.put('-',1); map.put('*',2); map.put('/',2); char [] chars=br.readLine().toCharArray(); //接收表达式并转换成字符数组 br.close(); for (int i = 0; i < chars.length; i++) { char c=chars[i]; if(Character.isDigit(c)){ //如果是数字类型的话 int x=0,j=i; while (j< chars.length && Character.isDigit(chars[j])){ x=x*10+chars[j]-'0'; j++; } nums.push(x); //数字入栈 i=j-1; }else if(c=='('){ //左括号直接入栈 ops.push(c); }else if(c==')'){ //遇到右括号代表括号结束计算括号里面的 while (ops.peek()!='(') { eval(); } ops.pop(); //左括号出栈 }else { //待入栈运算符优先级低，那么先计算就行 while(!ops.isEmpty() && ops.peek() != '(' && map.get(ops.peek()) >= map.get(c)){ eval(); } ops.push(c); //操作符入栈 } } while (!ops.isEmpty()) eval(); //剩余的进行计算 System.out.println(nums.peek()); } private static void eval() { int b=nums.pop(); int a=nums.pop(); char c=ops.pop(); if(c=='+') { nums.push(a+b); }else if(c=='-') { nums.push(a-b); }else if(c=='*'){ nums.push(a*b); }else { nums.push(a/b); } } }
易错点：
//第21行 while (j< chars.length && Character.isDigit(chars[j])){ x=x*10+chars[j]-'0'; j++; } nums.push(x); //数字入栈 i=j-1;
这个地方注意j是下标，是从i开始，判断是否是数字的时候要加上chars[]数组
这里i=j-1，i不能等于j，假如如果这个数字是两位数，那么j=2，i如果等于j，if结束后i++,i=3,就跳过一个字符了
//第36行 while(!ops.isEmpty() && ops.peek() != '(' && map.get(ops.peek()) >= map.get(c))
这个地方要加上判断栈顶不能为（
假设计算(1+3),先把(压栈到op进去，再把1压栈到num进去，接下来读取字符+，op栈里不为空为真（因为有(符号在栈里），判断栈顶元素不是左括号为假，假如不判断这个左括号的话，会继续执行while里的判断语句，把这个符号与栈顶元素的优先级比较，但是左括号没有优先级，会报错
————————————————
版权声明：本文为CSDN博主「小新要努力变强」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_68055637/article/details/128646977
