中缀表达式求值

分两步：

• 将我们人能理解的中缀表达式转换成计算机能理解的后缀表达式
• 进行后缀表达式计算出结果

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        ArrayList<String> res = toSuffix(s);
        return getVal(res);
    }

    /**
    * 将中缀表达式转化为 后缀表达式
    */
    public ArrayList<String> toSuffix(String infix){
        //定义运算符的优先级，方便后续进栈出栈的比较
        Map<Character, Integer> basic = new HashMap<Character, Integer>();
        basic.put('-', 1);
        basic.put('+', 1);
        basic.put('*', 2);
        basic.put('/', 2);
        basic.put('(', 0);//在运算中  （）的优先级最高，但是此处因程序中需要 故设置为0

        //放后缀表达式的list
        ArrayList<String> res = new ArrayList<>();
        //放运算符
        Stack<Character> stack = new Stack<>();

        //考虑到 操作数不仅是1位的，不能直接添加进结果 由len和temp来控制完整的操作数入栈
        int len = 0;
        String temp = "";

        //将运算符装起来，也是方便比较
        String standard = "*/+-(";

        //开始遍历
        for(int i = 0; i < infix.length(); i++){
            char ch = infix.charAt(i);
            //这个要放第一个判断
            if(ch == ')'){
                if(len > 0){
                    res.add(temp);
                }
                len = 0;
                temp = "";
                while(!stack.isEmpty() && stack.peek() != '('){ //将（ 之前的运算符弹出，添加进结果集
                    //res[cnt++] = stack.pop();
                    res.add(String.valueOf(stack.pop()));
                }
                stack.pop();
            }else if(Character.isDigit(ch)){ //如果是操作数 
                temp = temp + String.valueOf(ch);
                len++;
            }else if(standard.indexOf(ch) != -1){ //如果是运算符
                if(len > 0){
                    res.add(temp);
                }
                len = 0;
                temp = "";

                if(basic.get(ch) == 0 ){    //如果是 （
                    stack.push(ch);
                }else if(basic.get(ch) == 1){    //如果是 + - 
                    while(!stack.isEmpty() && basic.get(stack.peek()) >= 1){    //将 + - * / 运算符弹出
                        res.add(String.valueOf(stack.pop()));
                    }
                    //再入栈
                    stack.push(ch);
                }else if(basic.get(ch) == 2){    //如果是 * / 
                    while(!stack.isEmpty() && stack.peek() == 2){    //只需要弹出 / * 同级的
                        res.add(String.valueOf(stack.pop()));
                    }
                    //再入栈
                    stack.push(ch);
                }
            }
        }
        //最后还有保留的temp没有添加
        if(!temp.equals("")){
            res.add(temp);
        }
        //将栈中剩下的运算符也添加进去
        while(!stack.isEmpty()){
            res.add(String.valueOf(stack.pop()));
        }
        //再返回一个正确的后缀表达式
        return res;

    }
    /**
    *   利用栈来对后缀表达式求值
    */
    public int getVal(ArrayList<String> res){
        Stack<Integer> stack1 = new Stack<>();
        String ch; 
        int a, b;
        for(int i = 0; i < res.size(); i++){
            ch = res.get(i);
            //是运算符就从栈中取出操作数进行运算，再添加进栈
            if(ch.equals("+")){
                a = stack1.pop();
                b = stack1.pop();
                stack1.add(a+b);
            }else if(ch.equals("-")){
                a = stack1.pop();
                b = stack1.pop();
                stack1.add(b-a);
            }else if(ch.equals("*")){
                a = stack1.pop();
                b = stack1.pop();
                stack1.add(b*a);
            }else if(ch.equals("/")){
                a = stack1.pop();
                b = stack1.pop();
                stack1.add(b/a);
            }else{
                //不是运算符就入栈
                stack1.add(Integer.parseInt(ch));
            }
        }
        return stack1.peek();
    }

    }