【栈与队列】给定一个中缀表达式，请编写程序计算该表达式的值。（java）_7-3 表达式求值 分数 10 作者 朱允刚 单位 吉林大学 给定一个中缀表达式,请编写程

给定一个中缀表达式，请编写程序计算该表达式的值。表达式包含+、-、*、\、(、)，所有运算均为二元运算，操作数均为正整数，但可能不止一位，不超过5位。 运算结果为整数。 除法运算结果若为小数则进行截尾取整。若除法运算中除数为0，则输出ILLEGAL。

输入格式:

输入为一个字符串，表示中缀表达式。

输出格式:

输出为一个整数，为表达式的值；或者为一个字符串ILLEGAL。

输入样例:

5+(10*2)-6

输出样例:

19

输入样例:

8*(999+1)

输出样例:

8000

输入样例:

1+5/(1-1)

输出样例:

ILLEGAL

代码如下： 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String notation = scanner.next();
        //因为直接对String类型的字符串操作不方便，因此将其转换为对应的List;
        List<String> str1 = parseSuffixNotation(toInfixNotation(notation));
        if (calculate(str1)[1] == 1) {
            System.out.println(calculate(str1)[0]);
        } else {
            System.out.println("ILLEGAL");
        }
    }
 
    public static List<String> toInfixNotation(String s) {
        List<String> ls = new ArrayList<>();
        String str;
        char c;
        for (int i = 0; i < s.length(); i ++) {
            if (s.charAt(i) < 48 || s.charAt(i) > 57) {
                ls.add(s.charAt(i) + "");
            } else {
                str = "";
                int j = i;
                while (j < s.length() && s.charAt(j) >= 48 && s.charAt(j) <= 57) {
                    //但数字大于一位数时，i一定要再多往后移一位
                    if (j > i) {
                        i ++;
                    }
                    str += s.charAt(j);
                    j ++;
                }
                ls.add(str);
            }
        }
        return ls;
    }
 
    public static List<String> parseSuffixNotation(List<String> ls) {
        //符号栈
        Stack<String> s1 = new Stack<>();
        //存储中间结果的栈，因为在整个过程没有栈的弹出过程因此换为List
        List<String> s2 = new ArrayList<String>();
        for (String item: ls) {
            if (item.matches("\\d+") ) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();
            } else if (item.equals("+") || item.equals("-")) {
                int count = 0;
                while (s1.size() != 0) {
                    //当加减号入栈时，所有优先级不低于其的符号全部出栈，除非遇到括号
                    if (s1.peek().equals("(")) {
                        break;
                    }
                    s2.add(s1.pop());
                }
                s1.push(item);
            } else if (item.equals("*") || item.equals("/")) {
                s1.push(item);
            }
        }
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2;
    }
 
    public static int[] calculate(List<String> ls) {
        int n = 1;
        int[] arr = new int[2];
        Stack<Integer> stack = new Stack<>();
        Quit :
        for (int i = 0;i < ls.size(); i ++) {
            int a;
            int b;
            int result;
 
            switch (ls.get(i)) {
                case "+":
                    a = stack.pop();
                    b = stack.pop();
                    result = b + a;
                    stack.push(result);
                    break;
                case "-":
                    a = stack.pop();
                    b = stack.pop();
                    result = b - a;
                    stack.push(result);
                    break;
                case "*":
                    a = stack.pop();
                    b = stack.pop();
                    result = b * a;
                    stack.push(result);
                    break;
                case "/":
                    a = stack.pop();
                    b = stack.pop();
                    if (a == 0) {
                       n = 0;
                       break Quit;
                    }
                    result = b / a;
                    stack.push(result);
                    break;
                default:
                    stack.push(Integer.parseInt(ls.get(i)));
                    break;
            }
        }
        arr[0] = stack.pop();
        arr[1] = n;
        return arr;
    }
}