关于逆波兰计算器，需求如下
- 输入一个逆波兰表达式（后缀表达式），使用栈（Stack），计算其结果，只支持对整数的计算即可。
思路分析
后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后。
例如：
(3+4)×5−6
对应的后缀表达式是 3 4 + 5 × 6 -。
后缀表达式的计算机求值过程为从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和栈顶元素），并将结果入栈。重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
针对后缀表达式求值步骤如下
- 从左至右扫描，将3和4压入堆栈。
- 遇到+运算符，弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈。
- 将5入栈。
- 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈。
- 将6入栈。
- 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
代码实现
import java.util.ArrayList; import java.util.List; import java.util.Stack; /** * @author mengzhichao * @create 2022-04-19-9:27 */ public class PolandNotation { public static void main(String[] args) { //先定义给逆波兰表达式 (3+4)*5-6 => 3 4 + 5 * 6 - 为了方便，逆波兰表达式的数字和符号使用空格隔开 String suffixExpression = "3 4 + 5 * 6 -"; //思路 //1.先将"3 4 + 5 * 6 -"放入ArrayList中 //2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算 List<String> rpmList = getListString(suffixExpression); System.out.println("rpmList:"+rpmList); int res =calculate(rpmList); System.out.println(""+res); } //将一个逆波兰表达式，依次将数据和运算符，放入到ArrayList中 public static List<String> getListString(String suffixExpression){ //将 suffixExpression 分割 String[] split = suffixExpression.split(" "); List<String> list =new ArrayList<>(); for (String ele:split){ list.add(ele); } return list; } //完成对逆波兰表达式的运算 /** * 从左至右扫描，将3和4压入堆栈。 * 遇到+运算符，弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈。 * 将5入栈。 * 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈。 * 将6入栈。 * 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。 */ public static int calculate(List<String> ls){ //创建栈,只需要一个栈即可 Stack<String> stack = new Stack<>(); //遍历 ls for (String item:ls){ //这里使用正则表达式来取出数 if (item.matches("\\d+")){ //匹配的是多位数 //入栈 stack.push(item); } else { //pop出两个数，并运算，再入栈 int num2 =Integer.parseInt(stack.pop()); int num1 =Integer.parseInt(stack.pop()); int res = 0; if (item.equals("+")){ res = num1 + num2; } else if (item.equals("-")){ res = num1 - num2; }else if (item.equals("*")){ res = num1 * num2; }else if (item.equals("/")){ res = num1 / num2; }else { throw new RuntimeException("运算符有误"); } //把res入栈 stack.push(String.valueOf(res)); } } //最后留在stack中的数据就是运算结果 return Integer.parseInt(stack.pop()); } }
运行并测试
