129 公式字符串求值
Table of Contents

ac

给定一个字符串str，str表示一个公式，公式里可以有整数，加减乘除和左右括号，返回公式的计算结果（注意：题目中所有运算都是整型运算，向下取整,且保证数据合法，不会出现除0等情况）。

48*((70-65)-43)+8*1
-1816
              +
           /    \
        *         *
       /  \      /  \
    48     -    8    1
          / \
         -  43
       / \
     70 65

数字栈：48  70 65
符号栈：* （ （  -

数字栈：48  -38
符号栈：* +

遇到高，低优先级操作符号的处理

后缀表达式 & 中缀记法

3 + 5 * (2 - 4)

3 5 2 4 - * +

中缀表达式:48*((70-65)-43)+8*1
其转换成后缀表达式则为:48 70 65 - 43 - * 8 1 * +

中缀表达式:a + b*c + (d * e + f) * g
其转换成后缀表达式则为:a b c * + d e * f + g * +

a b c       =>  a b c * +   =>  a b c * + d e  =>  a b c * + d e * f + g * +
+ * 遇到+        +              + ( *               + *

ac

可参考学习：
https://www.cnblogs.com/lanhaicode/p/10776166.html

https://blog.csdn.net/weixin_44260779/article/details/90695746

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        String str = reader.readLine();
//        String str = "48*((70-65)-43)+8*1"; // -1816
//        String str = "3+1*4"; // 7
//        String str = "((11+10-13)+4-11+13-9+15+5*1+11-10-11-(4+10)-17+12+20+(6+20-10))"; // 32
//        String str = "((1-4+9+7*19)/18-(1-16+(11+17-18)))"; // 12
        int n = str.length();
        char[] chars = str.toCharArray();

        Stack<String> operatorSta = new Stack<>();
        Stack<String> integerStack = new Stack<>();

        String tmp = "";
        for(int i=0;i<n;i++){
            if(chars[i] == '('){
                operatorSta.push("(");
            }
            if(chars[i] == ')'){
                if(!tmp.isEmpty()){
                    integerStack.push(tmp);
                    tmp = "";
                }
                while (!operatorSta.isEmpty() && !operatorSta.peek().equals("(")){
                    integerStack.push(operatorSta.pop());
                }
                operatorSta.pop();
            }
            if(chars[i] == '*'){
                if(!tmp.isEmpty()){
                    integerStack.push(tmp);
                    tmp = "";
                }
                if(!operatorSta.isEmpty()){
                    if(operatorSta.peek().equals("(")){
                        // ( 优先级最高
                        operatorSta.push("*" );
                    }else if(operatorSta.peek().equals("+") || operatorSta.peek().equals("-")){
                        // 优先级高于栈顶运算符则压入堆栈
                        operatorSta.push("*");
                    }else {
                        // 将栈中优先级高的先弹出，直到优先级大于栈顶运算符或者栈空,再将该运算符入栈
                        while (!operatorSta.isEmpty() && (operatorSta.peek().equals("*") || operatorSta.peek().equals("/"))){
                            integerStack.push(operatorSta.pop());
                        }
                        operatorSta.push("*" );
                    }
                }else {
                    operatorSta.push("*");
                }
            }
            if(chars[i] == '/'){
                if(!tmp.isEmpty()){
                    integerStack.push(tmp);
                    tmp = "";
                }
                if(!operatorSta.isEmpty()){
                    if(operatorSta.peek().equals("(")){
                        // ( 优先级最高
                        operatorSta.push("/" );
                    }else if(operatorSta.peek().equals("+") || operatorSta.peek().equals("-")){
                        operatorSta.push("/");
                    }else {
                        while (!operatorSta.isEmpty() && (operatorSta.peek().equals("*") || operatorSta.peek().equals("/"))){
                            integerStack.push(operatorSta.pop());
                        }
                        operatorSta.push("/" );
                    }
                }else {
                    operatorSta.push("/");
                }
            }
            if(chars[i] == '+'){
                if(!tmp.isEmpty()){
                    integerStack.push(tmp);
                    tmp = "";
                }
                if(!operatorSta.isEmpty()) {
                    while (!operatorSta.isEmpty() && operatorSta.peek() != "(") {
                        integerStack.push(operatorSta.pop());
                    }
                    operatorSta.push("+");
                }else{
                    operatorSta.push("+");
                }
            }
            if(chars[i] == '-'){
                if(i == 0){
                    tmp += "-";
                }else if(chars[i-1] == '('){
                    tmp += "-";
                }else{
                    if(!tmp.isEmpty()){
                        integerStack.push(tmp);
                        tmp = "";
                    }
                    if(!operatorSta.isEmpty()) {
                        while (!operatorSta.isEmpty() && operatorSta.peek() != "(") {
                            integerStack.push(operatorSta.pop());
                        }
                        operatorSta.push("-");
                    }else{
                        operatorSta.push("-");
                    }
                }
            }
            if(chars[i] >= '0' && chars[i] <= '9'){
                tmp += chars[i];
            }
        }
        if(!tmp.isEmpty()){
            integerStack.push(tmp);
            tmp = "";
        }
        while (!operatorSta.isEmpty()){
            integerStack.push(operatorSta.pop());
        }
        Integer ans = calInfix(integerStack);
        System.out.print(ans);
    }

    // 计算中缀表达式
    static Integer calInfix(Stack<String> sta){
        List<String> list = new ArrayList<>(sta);
        Stack<Integer> ansStack = new Stack<>();
        for(int i=0;i<list.size();i++){
            if(list.get(i).equals("+") ||
                    list.get(i).equals("-") ||
                    list.get(i).equals("*") ||
                    list.get(i).equals("/")){
                Integer v2 = ansStack.pop();
                Integer v1 = ansStack.pop();
                Integer v = operator(list.get(i), v1, v2);
                ansStack.push(v);
            }else {
                ansStack.push(Integer.valueOf(list.get(i)));
            }
        }
        return ansStack.pop();
    }

    static Integer operator(String operate, Integer v1, Integer v2){
        if(operate.equals("+")){
            return v1 + v2;
        }
        if(operate.equals("-")){
            return v1 - v2;
        }
        if(operate.equals("*")){
            return v1 * v2;
        }
        if(operate.equals("/")){
            return v1 / v2;
        }
        return 0;
    }
}
/*
(1-20-7+4+18-4+10-9-11-2+11*20-2/7+17+19+8-13*8/3+(8+13*16)+((11+10-13)+4-11+13-9+15+5*1+11-10-11-(4+10)-17+12+20+(6+20-10))+5+13+20+15-9+18*2-1-19-16/3-8/20-19-3-8+8-17*11-(10+1)-11+1+13/17+(10+13-1*2/7)/12-9-3+2+11+16-15-4-7-16+1+9+((14+12*20/17-9-20-16+4)+4-12)-4/2-3*14+11+(7+10+4+13+16-15)-17/19-1+15+12+13+15+10+19+6+11+8*(20+13)+16+7-10+5+14+14+8-13-(11+(14-14*10+3+(5-7)-5/20-1+16)/(1-14-13*14+6+2+5+14+15+20+17)-(18-(17-18*4+10-(3-16-(9-15))+12)-4)-9-(11+(13+1)+20)*17+(17+6*8+16+6)+5))
1366

((11+10-13)+4-11+13-9+15+5*1+11-10-11-(4+10)-17+12+20+(6+20-10))
32

((10-8+9/10-19+7)+(7+4-10+1)+9-1+2+19-((10-3-4)+17)+17+6/15/16-(13+3+16+12+9-5/(9+2)-3-(11+13))+(16+7/2+3-2+7+2+15+13)+5-18-4+13-12-10+2+(13*2)-13-18-((1-4+9+7*19)/18-(1-16+(11+17-18)))+(15*9-(1-2)-15)-7-(4-15)+10/6-17-4+(11+3)-6-3-(15+2)+(8-11+12))+20+(8+1+10+12-15-15+7+14+12-20+(9+10-10+8-18-8+5+10+3+14+9))*(4+15+17+13+9-(18-7)-2*20+3+16-(18+3)-20-3-17+9-3+16)+6-7-(15-11/19+3-1+6-9-15+19+15-19-3-15-11+13-13+9+6-2-3-18+(11+8)-5-18+8-8-14-16-(10/1)*13-((5+1)+8*1+1+5-18-1/13+5)+9)-8
-292
*/