题解 | #表达式求值#
表达式求值
https://www.nowcoder.com/practice/9566499a2e1546c0a257e885dfdbf30d
// mark一下 import java.util.*; // 操作数栈 和 操作符栈 // 操作符运算优先级:+ - 小于 * / // ( 直接入栈 // 遇到)双栈出 进行运算 直到遇到( // 其他情况 数字直接入栈 符号优先级大于操作符栈顶元素入栈 否则进行运算 // 第一个-或者(后紧跟的- 表示负号 // 需要在字符串结尾加一个表示符号 处理当最后一个字符是数字时的情况 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextLine()) { String s = in.nextLine(); int length = s.length(); Stack<Integer> numStack = new Stack<>(); Stack<Character> opStack = new Stack<>(); String numStr = ""; for (int i = 0 ; i <= length; i++) { // 需要在字符串结尾加一个表示符号 处理当最后一个字符是数字时的情况 char c = i == length ? '$' : s.charAt(i); if (c >= '0' && c <= '9') { numStr += c; } else { // 开始遍历字符了 需要对之前的数字字符串转换并存入数字栈 if (numStr.length() > 0) { numStack.push(Integer.valueOf(numStr)); numStr = ""; } if (c == '+' || c == '-') { if (c == '-') { // 负数的情况 if (i == 0 || s.charAt(i - 1) == '(') { numStr = "-"; continue; } } while (!opStack.isEmpty() && ((opStack.peek() == '+') || (opStack.peek() == '-') || (opStack.peek() == '*') || (opStack.peek() == '/'))) { char curChar = opStack.pop(); int num2 = numStack.pop(); int num1 = numStack.pop(); numStack.push(calc(curChar, num1, num2)); } opStack.push(c); } else if (c == '*' || c == '/') { opStack.push(c); } else if (c == '(') { opStack.push(c); } else if (c == ')') { while (!opStack.isEmpty() && opStack.peek() != '(') { char curChar = opStack.pop(); int num2 = numStack.pop(); int num1 = numStack.pop(); numStack.push(calc(curChar, num1, num2)); } // 将(弹出 opStack.pop(); } } } while (!opStack.isEmpty()) { char curChar = opStack.pop(); int num2 = numStack.pop(); int num1 = numStack.pop(); numStack.push(calc(curChar, num1, num2)); } // 最终结果保存在操作数栈中 System.out.println(numStack.peek()); } } public static int calc(char c, int num1, int num2) { switch(c) { case '+': return num1 + num2; case '-': return num1 - num2; case '*': return num1 * num2; case '/': return num1 / num2; } return 0; } }