题解 | #四则运算#

中缀表达式转后缀表达式求值
后缀表达式就是声明两个栈，将操作符和操作数插入分别push操作数和操作符中，在操作符中遇到push操作符号优先级小于栈顶的数，那么将其出栈到操作数中，特殊字符：“{[(”等要遇到相反的才出栈且不放入操作数中。

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        while((line=br.readLine())!=null) {
            // List 存放后缀表达式
            List<String> list = new ArrayList<>();
            // 定义操作符栈stack，用于存放操作符 + - * / (
            Stack<Character> stack = new Stack<>();
            for(int i=0;i<line.length();i++) {
                // 定义一个字符，记录字符串当前循环的变量
                char c = line.charAt(i);
                // 取出以当前字符开头数字结尾的整数字符串进行判定是否为数字
                if (isNum(c)) {
                    int start = i; //记录开头数字的
                    if(i==line.length()-1) {
                        i++;     //加1，因为subString取值是前闭后开
                    }else {
                        while(isNum(line.charAt(++i))) {   //先加减再运算，因为subString取值是前闭后开
                        }
                    }
                    list.add(line.substring(start,i));
                    i--;
                }else if(c=='(' || c=='[' || c=='{') {  //为左括号，则入栈
                    stack.push(c);
                }else if(c==')' || c==']' || c=='}') {   //为右括号，则
                    while (stack.peek()!='(' && stack.peek()!='[' && stack.peek()!='{') {
                        list.add(String.valueOf(stack.pop()));
                    }
                    stack.pop();
                }else if(c=='-') {
                    //判断是减号还是负号
                    if((i!=0 && (isNum(line.charAt(i-1)) && isNum(line.charAt(i+1)))) || (line.charAt(i-1)==')' || line.charAt(i-1)==']' || line.charAt(i-1)=='}') || (line.charAt(i+1)=='(' || line.charAt(i+1)=='[' || line.charAt(i+1)=='{')) { //减号
                        // 优先级 小于 栈顶运算符
                        while(!greaterThan(c,stack)) {
                            list.add(String.valueOf(stack.pop()));
                        }
                        stack.push(c);
                    }else { //负号
                        int start = i;
                        while(isNum(line.charAt(++i))) {
                        }
                        list.add(line.substring(start,i));
                        i--;
                    }
                }else if(c=='+' || c=='*' || c=='/') {
                    while(!greaterThan(c, stack)) {
                        list.add(String.valueOf(stack.pop()));
                    }
                    stack.push(c);
                }
            }
            while(!stack.isEmpty()) {
                list.add(String.valueOf(stack.pop()));
            }

//            System.out.println(list.toString());
            //计算后缀表达式
            int result = calculate(list);
            System.out.println(result);
        }
    }
    //判断是否为数字
    public static boolean isNum(char c) {
        return (c>='0' && c<='9');
    }
    // 比较运算符与栈顶运算符的优先级
    public static boolean greaterThan(char c,Stack<Character> stack) {
        if(stack.isEmpty()) {
            return true;
        }else {
            char c1 =stack.peek();
            if(c=='*' || c=='/') {
                return !(c1=='*' || c1=='/');
            }else{
                return (c1=='(' || c1=='[' || c1=='{' );
            }
        }
    }
    public static int calculate(List<String> list) {
        // 定义数字栈，存放后缀表达式计算过程中的值
        Stack<Integer> stack = new Stack<>();
        int n1,n2;
        for (int i = 0; i < list.size(); i++) {
            switch (list.get(i)) {
            case "+":
                stack.push(stack.pop()+stack.pop());
                break;
            case "-":
                n1 = stack.pop();
                n2 = stack.pop();
                stack.push(n2-n1);
                break;
            case "*":
                stack.push(stack.pop()*stack.pop());
                break;
            case "/":
                n1 = stack.pop();
                n2 = stack.pop();
                stack.push(n2/n1);
                break;
            default:
                stack.push(Integer.parseInt(list.get(i)));
            }
        }
        return stack.pop();
    }
}