逆波兰算法计算器(手工传入后缀表达式)

逆波兰计算器

• 输入一个逆波兰表达式，使用栈，计算其结果
• 支持小括号和多位数整数，目前不包括小数

例如 (3+4)X5-6 对应的后缀表达式就是 34+5X6-,针对后缀表达式求值步骤如下：
1.从左至右扫描，将3和4压入堆栈
2.遇到+运算符，因此弹出4和3（4为栈顶元素，3为次栈顶元素），计算出3+4的值，得7，再将7入栈；
3.再将5入栈
4.接下来就是X运算符，因此弹出5和7，计算出5X7=35，将35入栈；
5.将6入栈；
6.最后是-运算符，计算出35-6的值，即29，由此得出最终结果

逆波兰计算器

package com.romanticlei.stack;

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class PolandNotation {

    public static void main(String[] args) {
        // 先定义一个逆波兰表达式
        // (3+4)x5-6 => 3 4 + 5 x 6 -
        // 说明：为了方便，逆波兰表达式和符号使用空格隔开
        String suffixExpression = "3 4 + 5 * 6 -";
        // 思路
        // 先将 "3 4 + 5 x 6 -" => 放到 ArrayList中
        // 将 ArrayList 传递给一个方法，然后遍历 ArrayList 配合栈完成计算

        System.out.println(getListString(suffixExpression));
        int res = calculate(getListString(suffixExpression));

        System.out.println("计算结果为： " + res);
    }

    // 将一个逆波兰表达式，依次将数据和运算符 放入到 ArrayList中
    public static List<String> getListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        List<String> list = Arrays.asList(split);

        return list;
    }

    // 完成对逆波兰表达式的运算
    public static int calculate(List<String> list){
        Stack<String> stack = new Stack<>();
        // 遍历集合 list
        for (String item : list) {
            // 判断是否是数字
            if (item.matches("\\d+")){
                stack.push(item);
            } else {
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if ("+".equals(item)){
                    res = num1 + num2;
                } else if ("-".equals(item)){
                    res = num1 - num2;
                } else if ("*".equals(item)){
                    res = num1 * num2;
                } else if ("/".equals(item)){
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("无法识别的运算符");
                }
                stack.push(String.valueOf(res));
            }
        }
        return Integer.parseInt(stack.pop());
    }
}