解题思路:(双栈设计)

  • 1. 数字直接入栈
  • 2. 如果是运算符,对比当前运算符和栈顶元素优先级,
  • 如果是减号,且前面是'(' ,则说明该数字为负数,数字栈push 0,作为运算。
  • 当前的高则直接入栈
  • 当前的低: 则弹出栈顶运算符 并在数字栈中弹出两个元素计算 结果压入数字栈, 当先低的压入栈中。
  • 3. 如果是'(' 直接入栈,直到 ')',弹出俩个数字和运算符 并计算
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {
            String str = in.next();
            // 代替所有的括号
            str = str.replace("{", "(").replace("}", ")")
                  .replace("[", "(").replace("]", ")");

            // 数字栈
            Stack<Integer> num = new Stack<>();
            // 运算符栈
            Stack<Character> symbol = new Stack<>();

            // 加入括号的处理,保证最终会处理完整个表达式
            symbol.push('(');
            str = str + ")";

            for (int i = 0; i < str.length(); i++) {
                char value = str.charAt(i);

                // 数字 直接压入数组栈
                if (Character.isDigit(value)) {
                    // 截取数字
                    int j = i;
                    while (Character.isDigit(str.charAt(i)) && i < str.length()) {
                        i++;
                    }
                    // 左闭右开
                    int number = Integer.parseInt(str.substring(j, i));
                    num.push(number);
                    i--;
                } else if (value == '+' || value == '*' || value == '/' || value == '-') {
                    // 处理负数的情况 加零
                    if (value == '-' && str.charAt(i - 1) == '(') {
                        num.push(0);
                    }

                    // 优先级比较 -------当前的运算符 优先级低时, 迭代
                    while (symbol.size() > 1 && num.size() > 0 &&
                            getEvaluationPriority(symbol.peek(), value)) {
                        getEvaluationValue(num, symbol);
                    }
                    symbol.push(value);
                } else if (value == '(') {
                    symbol.push(value);
                } else if (value == ')') {
                    // 迭代,直到遇到'('
                    while (symbol.peek() != '(') {
                        getEvaluationValue(num, symbol);
                    }
                    // 弹出左括号
                    symbol.pop();
                }
            }

            System.out.println(num.pop());
        }
    }

    // 比较运算符的优先级
    // a 栈顶元素  b当前符号,a高返回false;
    public static boolean getEvaluationPriority(Character a, Character b) {
        // 任何符号遇到'(' 符号直接入栈,
        if (a == '(') return false;
        else if ((a == '+' || a == '-') && b == '*' || b == '/') return false;
        return true;
    }

    // 两个栈 做运算
    public static void getEvaluationValue(Stack<Integer> num,
                                          Stack<Character> symbol) {
        int b = num.pop();
        int a = num.pop();
        int s = symbol.pop();
        switch (s) {
            case '+':
                a = a + b;
                break;
            case '-':
                a = a - b;
                break;
            case '*':
                a = a * b;
                break;
            case '/':
                a = a / b;
                break;
        }
        // 计算结果入栈
        num.push(a);
    }
}