java實作中綴表達式轉字尾表達式并輸出運算結果

原則：數字輸出，運算符進棧，括号比對出棧，棧頂優先級低不出棧

public class postfix {

    public static String[] outPostfix(String[] infix){
        String[] postfix = new String[100];
        int index = 0;
        int bracket = 0; //标記括号的對數
        Map operatorMap = new HashMap<>(); // 用hashmap存儲每個運算符的優先度
        operatorMap.put("+", 1);
        operatorMap.put("-", 1);
        operatorMap.put("*", 2);
        operatorMap.put("/", 2);
        Stack<String> postfixStack = new Stack<>(); //用于存儲字尾算法的運算符
        for (int i = 0; i < infix.length && infix[i] != null; i++) {
            String current = infix[i];
            if (current.charAt(0) >= '0' && current.charAt(0) <= '9'){ //遇到數字直接放入字尾數組
                postfix[index++] = current;
            }else {
                if (postfixStack.isEmpty()){ //保證字尾運算符棧不為空
                    postfixStack.push(current);
                }
                /* *
                *如果括号已經全部處理，而且目前字元不是括号，
                *字尾運算符棧頂不是括号，并且棧頂運算符優先度小于目前運算符優先度，
                *将目前周遊運算符後邊的數字放入字尾數組中，再将目前運算符放入字尾數組中。
                */
                else if (bracket == 0 && !isBracket(current) &&
                        !isBracket(postfixStack.peek()) &&
                        Integer.parseInt(String.valueOf(operatorMap.get(postfixStack.peek()))) < Integer.parseInt(String.valueOf(operatorMap.get(current)))){
                    postfix[index++] = infix[i + 1];
                    postfix[index++] = infix[i];
                    i++;
                }
                /**
                 * 同理 棧頂運算符優先度大于等于目前運算符優先度,
                 *将棧頂運算符放入字尾數組中，再将目前周遊的運算符放入棧中
                 */
                else if (bracket == 0 && !isBracket(current) &&
                        !isBracket(postfixStack.peek()) &&
                        Integer.parseInt(String.valueOf(operatorMap.get(postfixStack.peek()))) >= Integer.parseInt(String.valueOf(operatorMap.get(current)))){
                    postfix[index++] = postfixStack.pop();
                    postfixStack.push(current);
                }
                else {
                    if (current.equals("(")) bracket++; // 若遇到左括号，bracket加1
                    postfixStack.push(current);
                    if (postfixStack.peek().equals(")")){ //遇到右括号，bracket減1，同時将棧中括号間的運算符出棧
                        bracket--;
                        postfixStack.pop();
                        while (!postfixStack.peek().equals("(")){
                            postfix[index++] = postfixStack.pop();
                        }
                        postfixStack.pop();
                    }
                }
            }
        }
        while (!postfixStack.isEmpty()) postfix[index++] = postfixStack.pop();
        return postfix;
    }
    public static double result(String[] postfix){
        double result = 0;
        Stack<Double> computeStack = new Stack();
        for (int i = 0; i < postfix.length && postfix[i] != null; i++) {
            String current = postfix[i];
            //目前字元為數字，則入棧
            if (current.charAt(0) >= '0' && current.charAt(0) <= '9'){
                computeStack.push(todouble(current));
            }
            //目前字元為運算符，從棧頂取出兩個數字運算出結果，并放入棧中
            else {
                switch (current){
                    case "+": result = computeStack.pop() + computeStack.pop();
                    computeStack.push(result);break;
                    case "-": result = -(computeStack.pop() - computeStack.pop());
                    computeStack.push(result);break;
                    case "*": result = computeStack.pop() * computeStack.pop();
                    computeStack.push(result);break;
                    case "/": result = 1 / (computeStack.pop() / computeStack.pop());
                    computeStack.push(result);break;
                    default: break;
                }
            }
        }
        return result;
    }
    public static double todouble(String str){
        double num = 0;
        num = Double.valueOf(Integer.parseInt(str));
        return num;
    }
    public static boolean isBracket(String str){
        if (str.equals("(") || str.equals(")")) return true;
        else return false;
    }
    public static void main(String[] args){
        String[] infix = new String[]{"9", "+", "(", "3",  "-", "1", ")", "*", "3", "+", "10", "/", "2"};
        String[] infix1 = new String[100];
        int i = 0;
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            infix1[i++] = in.nextLine();
        }
        in.close();
        infix = outPostfix(infix1);
        for (i = 0; i < infix.length && infix[i] != null; i++) {
            System.out.print(infix[i] + " ");
        }
        System.out.print("\n");
        System.out.println(result(infix));
    }
}
           

輸入：

2

*

(

3

+

3

*

(

5

+

4

)

)

字尾表達式：

2 3 3 5 4 + * + * 

結果：60.0