数据结构与算法-栈-逆波兰计算器

package stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


public class PolandCalulator {

    public static void main(String[] args) {
//        //后缀表达式
//        String expression = "3 2 5 * + 2 5 * -";
//        handleData(expression);
        // 1 + (( 2 + 3) * 4) - 5
        // 1 2 3 + 4 * + 5 -
        //中缀表达式
        String expression = "1 + (( 2 + 3 ) * 4) - 5";
        //将中缀表达式转换为list
        List list = toexpressionList(expression);
        System.out.println(list);
        //将中缀表达式转为后缀表达式
        String data = toSuffixexpression(list);
        System.out.println(data);
        //计算表达式的值
        handleData(data);
    }

    
    public static void handleData(String str) {
        String[] strs = str.split(" ");
        Stack stack = new Stack<>();
        for (String s : strs) {
            if (s.matches("\d+")) {
                stack.push(s);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int result = calculate(num1, num2, s);
                stack.push(result + "");
            }
        }
        System.out.printf("计算结果是：%s n", stack.pop());
    }

    
    public static int calculate(int num1, int num2, String ch) {
        int result = 0;
        switch (ch) {
            case "+":
                result = num1 + num2;
                break;
            case "-":
                result = num2 - num1;
                break;
            case "*":
                result = num1 * num2;
                break;
            case "/":
                result = num2 / num1;
                break;
        }
        return result;
    }

    
    public static List toexpressionList(String s) {
        //去除空格
        s = s.replace(" ", "");
        List data = new ArrayList<>();
        //遍历的索引
        int i = 0;
        //当前字符
        char ch;
        while (i < s.length()) {
            ch = s.charAt(i);
            //非数字直接放入数组
            if (ch < 48 || ch > 57) {
                data.add(ch + "");
                i++;
            } else {
                //如果是数字继续遍历后面的，直到为非数字结束循环
                StringBuilder keepNum = new StringBuilder();
                while (i < s.length() && isNumber(s.charAt(i))) {
                    keepNum.append(s.charAt(i));
                    i++;
                }
                //将数字放入数组
                data.add(keepNum.toString());
            }
        }
        return data;
    }

    
    public static boolean isNumber(char num) {
        return num >= 48 && num <= 57;
    }

    
    public static String toSuffixexpression(List list) {
        Stack s1 = new Stack<>();
        List s2 = new ArrayList<>();
        for (String item : list) {
            if (item.matches("\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                //如果是右括号，则依次弹出s1栈顶的运算符，并压入栈s2，知道遇到左括号为止，并将这对括号丢弃
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                //清除左括号
                s1.pop();
            } else {
                //当item的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入到s2中，再次转到4.1与s1中新的栈顶运算符比较
                while (s1.size() != 0 && getPriority(item) <= getPriority(s1.peek())) {
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }
        //将s1中剩余的运算符依次弹出并加入s2
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return String.join(" ", s2);
    }

    
    public static int getPriority(String character) {
        switch (character) {
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
            default:
                return -1;
        }
    }
}