题解 | #表达式求值#

双栈法解题

• 需要维护一个操作数栈，一个操作符栈，一个操作符优先级的map。
• 需要维护一个计算函数，操作符栈弹出一个操作和操作数栈弹出的两个操作数进行运算，运算结果再进入操作数栈。
• 如果遇到数字则将该数字后面连着的数字都读取后拼接成完整的数字再进操作数栈。
• 如果遇到操作符则先根据运算符优先级map，如果栈内运算符优先级比当前运算符优先级高或相等，则进入计算函数计算，直到栈顶运算符优先级比当前运算符优先级低，再将当前操作符进操作符栈。
• 如果遇到左括号直接进操作符栈，如果遇到右括号则进入计算函数中计算，直到操作符栈弹出左括号。

注意事项

• 由于第一个数可能是负数，为了减少边界判断，操作符栈初始时要添加一个0。
• 为防止 () 内出现的首个字符为运算符，将所有的空格去掉，并将 (- 替换为 (0-，(+ 替换为 (0+。

参考

*************************************************************************

/*
 * @Author: LibraStalker **********
 * @Date: 2023-08-18 12:18:55
 * @FilePath: Solution.java
 * @Description: 
 */
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    private void calc(Stack<Character> opStack, Stack<Integer> numStack) {
	  	// 操作符栈有元素以及操作数栈至少有两个元素才可以进行计算
        if(numStack.isEmpty() || numStack.size() < 2) {
            return;
        }
        if(opStack.isEmpty()) {
            return;
        }
        Character op = opStack.pop();
        Integer a = numStack.pop(), b = numStack.pop();
        Integer ans = 0;
        switch(op) {
            case '+':
                ans = a + b;
                break;
            case '-':
                ans = b - a;
                break;
            case '*':
                ans = a * b;
                break;
        }
        numStack.push(ans);
    }
    public int solve (String s) {
        // write code here
        Stack<Character> opStack = new Stack<>();  // 操作符栈
        Stack<Integer> numStack = new Stack<>();  // 操作数栈
        Map<Character, Integer> map = new HashMap<>();  // 运算符优先级
        map.put('-', 1);
        map.put('+', 1);
        map.put('*', 2);
        numStack.push(0);
        for (int i = 0; i < s.length(); ++i) {
            Character currentChar = s.charAt(i);
            if(Character.isDigit(currentChar)) {  // 如果遇到数字，就将后面连续的数字拼接成完整的数字，然后进入操作数栈
                StringBuilder numStr = new StringBuilder(currentChar.toString());
                i++;
                while(i < s.length() && Character.isDigit(s.charAt(i))) {
                    numStr.append(s.charAt(i));
                    ++i;
                }
                i--;
                numStack.push(Integer.parseInt(numStr.toString()));
            }
            else if(currentChar == '(') {  // 如果遇到左括号，直接入操作符栈
                opStack.push(currentChar);
            }
            else if(currentChar == ')') {  // 如果遇到右括号，将操作符栈的运算符弹出进行计算，直到弹出左括号
                while(!opStack.isEmpty()) {
                    if(opStack.peek() != '(') {
                        calc(opStack, numStack);
                    }
                    else {
                        opStack.pop();
                        break;
                    }
                }
            }
            else {  // 如果遇到操作符，则先将操作符栈内优先级较高或相等的运算符先计算完再入栈
                while(!opStack.isEmpty() && opStack.peek() != '(') {
                    if (map.get(currentChar) <= map.get(opStack.peek())) {
                        calc(opStack, numStack);
                    }
                    else {
                        break;
                    }
                }
                opStack.push(currentChar);
            }
        }
        while(!opStack.isEmpty() && opStack.peek() != '(') {  // 如果操作符栈还有操作符，则将剩下的内容计算完
            calc(opStack, numStack);
        }

        return numStack.peek();
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.solve("12+3*20"));
    }
}