小猿的算术表达式

import java.util.*;

public class Main {

/*
    1.将带括号的表达式转为不带括号的后缀表达式
        ( 1)遇到左括号和运算符运算符入栈，
        （2）遇到右括号弹出运算符直到左括号，弹出的运算符放到表达式
        （3）遇到数字直接加入表达式
    2. 计算不带括号的后缀表达式
        （1）遇到数字入数字栈
        （2）遇到操作符从栈中弹出两个数字计算
*/
    static Map<Character,Integer> priorityMap= new HashMap<>();

    public static void main(String[] args){
        Scanner scanner= new Scanner(System.in);
        priorityMap.put('+',1);
        priorityMap.put('-',1);
        priorityMap.put('*',2);
        priorityMap.put('/',2);
        priorityMap.put('(',0);
        priorityMap.put(')',0);

    
        int index=0;
        int N= scanner.nextInt();
        //第一个输入是数字
        //第二个输入是带空格的字符串，要用nextLine()接收
        
        //注意nextLine会接收到数字之后的"\n"，要额外使用一个scanner.nextLine()接收该空行
        //真烦死了，这个sb输入
        String emptyLine= scanner.nextLine();
        while(scanner.hasNext()){
            index++;
            String preFix= scanner.nextLine();
            //System.out.println(preFix);
            List<String> postFix= getPostFix(preFix);
            //null说明表达式不合法
            if(postFix==null){
                System.out.println("invalid");
            }else{
                long value= calculate(postFix);
                if(value==-1){
                    System.out.println("invalid");
                }else{
                    System.out.println(value%10000000);
                }
                
            }

            //System.out.println("-----");
        }

    }
    


    public static long  calculate(List<String> postFix){
        Stack<Long> numStack= new Stack<>();
        for(int i=0;i<postFix.size();i++){
            String curStr= postFix.get(i);
            if(checkOpt(curStr)){
                long numAfter= numStack.pop()%10000000;;
                long numBefore= numStack.pop()%10000000;
                if(curStr.equals("+")){
                    numStack.push((numBefore+numAfter)%10000000);
                }
                if(curStr.equals("-")){
                    numStack.push((numBefore-numAfter)%10000000);
                }
                if(curStr.equals("*")){
                    numStack.push((numBefore*numAfter)%10000000);
                }
                if(curStr.equals("/")){
                    numStack.push((numBefore/numAfter)%10000000);
                }
            }else{
                numStack.push(Long.parseLong(curStr));
            }
        }
        if(numStack.size()>1){
            return -1;
        }
        return numStack.pop()+10000000;
    }


    public static List<String> getPostFix(String preFix){
        Stack<Character> optStack= new Stack<>();
        //System.out.println(preFix);
        List<String> postFix= new ArrayList<>();
        for(int i=0;i<preFix.length();i++){
            char cur= preFix.charAt(i);
            if(cur=='('){
                optStack.push(cur);
            }else if(cur==' '){
                continue;
                //数字直接作为表达式
            }else if(Character.isDigit(cur)){
                int loc= i;
                while(loc<preFix.length()){
                    char curChar= preFix.charAt(loc);
                    if(!Character.isDigit(curChar)){
                        break;
                    }
                    loc++;
                }
                //数字
                String digits= preFix.substring(i,loc);
                i=loc-1;
                postFix.add(digits);

            }else if(cur==')'){
                //System.out.println("右括号)");
                while(!optStack.isEmpty() && optStack.peek()!='('){
                    postFix.add(String.valueOf(optStack.pop()));
                }
                if(optStack.isEmpty()){
                    return null;
                    //弹出左括号
                }else{
                    //System.out.println(optStack.peek());
                    optStack.pop();
                }
                //+-*/运算符
            }else if(checkOpt(String.valueOf(cur))){
                String curString=String.valueOf(cur);
                if(optStack.isEmpty() ){
                    optStack.push(cur);
                }else{
                    while(!optStack.isEmpty() && priorityMap.get(optStack.peek())>=priorityMap.get(cur)){
                        postFix.add(String.valueOf(optStack.pop()));
                    }
                    optStack.push(cur);
                }

            }
        }

        return postFix;
    }

    public static boolean checkOpt(String str){
        return (str.equals("+") || str.equals("-")
                ||str.equals("*")||str.equals("/"));
    }


}