[Java知识库]栈实现后缀表达式

ArrayStack 代码来自

public class PolandNotation {

    public static void main(String[] args) {
        System.out.println(calculate("4 5 * 8 - 60 + 8 2 / +"));
        System.out.println(calculate2(list2PolandList(expression2List("1+((2+3)*4)-5"))));
        System.out.println(calculate2(list2PolandList(expression2List("7*2-2-5+10-5+8/4"))));
    }


    public static int calculate(String expression) {
        String[] s = expression.split(" ");
        ArrayStack arrayStack = new ArrayStack(10);
        for (String s1 : s) {
            if (ArrayStack.isOper(s1.charAt(0))) {
                int num1 = arrayStack.pop();
                int num2 = arrayStack.pop();
                int calc = ArrayStack.calc(num1, num2, s1.charAt(0));
                arrayStack.push(calc);
            } else {
                arrayStack.push(Integer.parseInt(s1));
            }
        }
        return arrayStack.pop();
    }

    /**
     * 计算后缀表达式集合
     *
     * @param list
     * @return
     */
    public static int calculate2(List<String> list) {
        ArrayStack arrayStack = new ArrayStack(10);
        for (String s1 : list) {
            if (ArrayStack.isOper(s1.charAt(0))) {
                int num1 = arrayStack.pop();
                int num2 = arrayStack.pop();
                int calc = ArrayStack.calc(num1, num2, s1.charAt(0));
                arrayStack.push(calc);
            } else {
                arrayStack.push(Integer.parseInt(s1));
            }
        }
        return arrayStack.pop();
    }

    /**
     * 将表达式转换成集合
     *
     * @param expression
     * @return
     */
    public static List<String> expression2List(String expression) {
        List<String> list = new ArrayList<>();
        int i = 0;
        String str = "";
        char c;
        do {
            // 非数字
            if (expression.charAt(i) < 48 || expression.charAt(i) > 57) {
                list.add("" + expression.charAt(i));
                i++;
            } else {
                // 数字，判断是否是多位数，多位数就拼接
                while (i < expression.length() && expression.charAt(i) >= 48 && expression.charAt(i) <= 57) {
                    str += expression.charAt(i);
                    i++;
                }
                list.add(str);
                // 记得将str置空
                str = "";
            }
        } while (i < expression.length());
        return list;
    }

    /**
     * 将表达式转换成集合的集合转换成后缀表达式集合
     *
     * @param list
     * @return
     */
    public static List<String> list2PolandList(List<String> list) {
        // 符号栈
        ArrayStack2 stack = new ArrayStack2(10);
        // 数字集合
        List<String> polandList = new ArrayList<>();
        for (String s : list) {
            if (s.matches("\\d+")) {
                polandList.add(s);
                // 左括号直接入符号栈
            } else if ("(".equals(s)) {
                stack.push(s.charAt(0));
                // 右括号则将符号栈中的符号压入数字栈知道左括号为止
            } else if (")".equals(s)) {
                while (!"(".equals(String.valueOf(stack.peek()))) {
                    polandList.add(String.valueOf(stack.pop()));
                }
                // 将左括号弹出符号栈
                stack.pop();
            } else {
                // 其他符号，判断优先级。如果符号栈栈顶元素的优先级大于等于当前元素的优先级，则将符号栈栈顶元素弹出压入数字栈
                while (stack.getTop() >= 0 && ArrayStack.getPriority(stack.peek()) >= ArrayStack.getPriority(s.charAt(0))) {
                    polandList.add(String.valueOf(stack.pop()));
                }
                // 将当前符号压入数字栈
                stack.push(s.charAt(0));
            }
        }
        // 将符号栈的剩余元素全部压入数字栈
        while (stack.getTop() >= 0) {
            polandList.add(String.valueOf(stack.pop()));
        }
        return polandList;
    }
}

创作挑战赛

新人创作奖励来咯，坚持创作打卡瓜分现金大奖