题解 | #表达式求值#
表达式求值
https://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4
import java.util.*; public class Solution { //主要思路 栈s1存左括号、运算符 栈s2存数字 利用括号匹配来进行运算 //设置优先级 Map<Character, Integer> map = new HashMap<Character, Integer>() { { put('-', 1); put('+', 1); put('*', 2); put('/', 2); put('%', 2); put('^', 3); } }; int index = 0; //index 指向当前String中的字符 //利用栈1的运算符和栈2的数字 进行运算 public void getSum(Deque<Character> s1, Deque<Integer> s2) { if (s1.isEmpty()) return; if (s2.isEmpty() || s2.size() < 2) return; int sum = 0; char tempChar = s1.pollLast(); int a = s2.pollLast(); int b = s2.pollLast(); switch (tempChar) { case '+': sum = a + b; break; case '-': sum = b - a; break; case '*': sum = a * b; break; case '/': sum = a / b; break; } s2.addLast(sum);//运算后得到的结果sum要压入栈2中 } //通过字符串得到数字 public void getInt(Deque<Integer> s2, String s) { if (s.charAt(index) >= '0' && s.charAt(index) <= '9') { int j = index; int tempInt = 0; while (j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9') { tempInt = tempInt * 10 + s.charAt(j) - '0'; j++; } s2.addLast(tempInt); index = j - 1; } } //判断当前字符是否是数字字符 public boolean isNumber(char c) { return Character.isDigit(c);//用于判断当前字符是否是数字字符 } public int solve(String s) { //左括号和运算符加入栈1中 //数字加入到栈2中 //如果栈1匹配到右括号那么弹出一个运算符 然后栈2弹出两个数字 进行运算 直到栈1的顶是左括号停止 //这里ArrayDeque可以当栈或者双端队列来用 并且它的效率更高 Deque<Character> s1 = new ArrayDeque<>(); Deque<Integer> s2 = new ArrayDeque<>(); while (index < s.length()) { //"(2*(3-4))*5" if (s.charAt(index) == '(') { //匹配到左括号 s1.addLast(s.charAt(index)); index++; } else if (s.charAt(index) == ')') { //匹配到右括号 while (!s1.isEmpty()) { if (s1.peekLast() != '(') { //如果s1栈顶不是左括号 getSum(s1, s2); //那么就进行运算 } else { //直到遇到第一个左括号的时候 左括号弹出栈1 break; s1.pollLast(); break; } } index++;//同时往后继续找字符 } else { //匹配到其他字符 if (isNumber(s.charAt(index))) { //匹配到是数字字符 getInt(s2, s); //得到数字 并把它压入栈2中 index++;//同时往后继续找字符 } else { //匹配到运算符 while (!s1.isEmpty() && s1.peekLast() != '(') { char prev = s1.peekLast(); //把s1的栈顶元素先给prev if (map.get(prev) >= map.get(s.charAt(index))) { //进行判断优先级 //如果当前运算符优先级比prev的优先级低 getSum(s1, s2); //那就把之前的运算符和数字先进行计算 } else { //如果优先级不小 那么出循环 break; } } s1.addLast(s.charAt(index));//压入栈s1; index++;//同时往后继续找字符 } } } while (!s1.isEmpty() && s1.peekLast() != '(') getSum(s1, s2); //如果栈s1仍然有元素并且栈顶元素不是左括号 那么就进行运算; return s2.peekLast();//最后得到的s2栈只有一个数字就是运算后的结果 } }