题解 | #表达式求值#

import java.util.*;

/**
  双栈直接求解,核心思想是:先把运算符优先级高的两侧的数字算出,先把优先级高的运算符入栈,
  下次遇到优先级低的运算符时,就计算该运算符前面的优先级较高的运算符两侧的数字
 */
public class Solution {

  /**计算运算符的优先级 */
  boolean grade(char op1, char op2) {//比较当前运算符(op1)和栈顶运算符(op2)的优先级
    if (op1 == '*') return true;
    if (op2 == '*') return false;
    if (op1 == '-' && op2 == '-') return false;
    return true;
  }
  /**计算数值 */
  int calc(Stack<Integer> nums, char op) {
    int result = 0;
    if (nums.size() >= 2) {//当数字栈中的元素大于2时的计算方式
      int a = nums.pop();
      int b = nums.pop();
      switch (op) {
        case '+':
          result = b + a;
          break;
        case '-':
          result = b - a;
          break;
        case '*':
          result = b * a;
          break;
      }
    } else {//当数字栈中只有一个元素时,此时操作符栈中的元素为'+'或'-',处理当测试用例为"-1"或"+1"的情况
      result = nums.pop();
      if (op == '-') result = -result;
    }
    return result;
  }
  /**判断是否为数字 */
  boolean isNum(char c) {
    if (c - '0' >= 0 && c - '0' <= 9) return true;
    return false;
  }
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   * 返回表达式的值
   * @param s string字符串 待计算的表达式
   * @return int整型
   */
  Stack<Integer> nums = new Stack<>();
  Stack<Character> ops = new Stack<>();

  public int solve (String s) {
    int result = 0;
    int flag = 0;//记录是否连续读入了多个数字字符,处理输入为:"12+100"的情况
    // write code here
    for (int i = 0; i < s.length(); i++) {
      if (isNum(s.charAt(i))) {//当前字符是数字,则加入数字栈中
        if (flag == 1) {//第二至多次遇到数字字符
          int temp = nums.pop() * 10;
          nums.push(temp + (s.charAt(i) - '0'));
        } else {//第一次遇到数字字符
          nums.push(s.charAt(i) - '0');
          flag = 1;
        }
      } else if (s.charAt(i) == '(') {//遇到左括号,直接压入操作符栈
        flag = 0;//表示当前字符为运算符
        ops.push(s.charAt(i));
      } else if (s.charAt(i) == ')') {//遇到右括号,需要将该右括号前的表达式算出
        flag = 0;
        while (ops.peek() != '(') {//凡是加入运算符栈的字符,这样的表达式都满足后缀表达式,因此按照出栈顺序就可算出
          nums.push(calc(nums, ops.pop()));
        }
        ops.pop();//将左括号弹出
      } else if (ops.isEmpty() || grade(s.charAt(i), ops.peek())) {//优先级高的运算符入栈
        flag = 0;
        ops.push(s.charAt(i));
      } else {//遇到优先级低的运算符,需要将该运算符前面的优先级高的运算符所表示的表达式计算出来
        flag = 0;
        while (!grade(s.charAt(i), ops.peek())) {
          nums.push(calc(nums, ops.pop()));
          if (ops.size() == 0) break;//有可能最后一个运算符出栈后,栈就空了,再去判断循环条件时,会出现空栈异常
        }
        ops.push(s.charAt(i));//优先级低的运算符入栈
      }
    }
	//以上循环结束后,运算符栈中只有'+'或'-'了,直接按后缀表达式计算计算即可
    while (!ops.isEmpty()) {
      nums.push(calc(nums, ops.pop()));
    }
    return nums.peek();
  }

}