前言

逆波兰计算器是用逆波兰表达式实现的一个计算器，逆波兰表达式又叫后缀表达式，我们使用该计算器时输入的是中缀表达式，然后计算器会把中缀表达式转成后缀表达式，这样更有利于计算器的运算，计算器使用的数据结构是栈。

一、功能要求

写一个控制台计算器，能够进行简单的加减乘除运算，支持小括号，要求使用逆波兰表达式实现。

二、思路分析

首先我们把输入的中缀表达式字符串存入list集合，操作集合中的元素比直接操作字符串更方便，然后我们再把中缀表达式的集合形式转成后缀表达式的集合形式，接下来就可以调用我们的计算函数进行计算。

三、中缀表达式转后缀表达式

中缀表达式转后缀表达式的核心思想也是借助了一个栈来进行操作，大家可以仔细看图中转的过程，并结合代码深入理解。

四、计算过程

计算过程并不复杂，相信大家学会了转后缀表达式后就能很轻易的实现该操作。

五、时间复杂度

逆波兰计算器的时间复杂度应该为O(n)

六、代码实现

1.测试代码

代码如下：

package com.yc.stack;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;public class PolandNotation {public static void main(String[] args) {Scanner sc = new Scanner(System.in);boolean flag = true;while(flag){System.out.println("请输入表达式：");//1+((2+3)*4)-5String expression = sc.next();//中缀表达式字符串转为list集合形式List<String> infixExprssion = toInfixExpressionList(expression);//中缀表达式转后缀表达式List<String> sufixExpression = parseSufixExpressionList(infixExprssion);//调用计算函数求解int res = calculate(sufixExpression);System.out.println(res);}sc.close();}/*** 中缀表达式字符串转集合形式* @param infixExprssion 中缀表达式字符串* @return*/private static List<String> parseSufixExpressionList(List<String> infixExprssion) {Stack<String> stack = new Stack<String>();List<String> list = new ArrayList<String>();for(String item:infixExprssion){if(item.matches("\\d+")){list.add(item);}else if(item.equals("(")){stack.push(item);}else if(item.equals(")")){while(!stack.peek().equals("(")){list.add(stack.pop());}stack.pop();}else{while(!stack.isEmpty()&&Operation.priority(stack.peek())>=Operation.priority(item)){list.add(stack.pop());}stack.push(item);}}while(!stack.isEmpty()){list.add(stack.pop());}return list;}/*** 中缀表达式转后缀表达式* @param expression 中缀表达式集合形式* @return*/private static List<String> toInfixExpressionList(String expression) {List<String> list = new ArrayList<String>();int index = 0;String str;do{if(expression.charAt(index)<48||expression.charAt(index)>57){list.add(expression.charAt(index)+"");index++;}else{str = "";while(index<expression.length()&&(expression.charAt(index)>=48&&expression.charAt(index)<=57)){str += expression.charAt(index);index++;}list.add(str);}}while(index<expression.length());return list;}/*** 计算求解* @param list 后缀表达式* @return*/private static int calculate(List<String> list) {Stack<String> stack = new Stack<String>();for(String item:list){if(item.matches("\\d+")){stack.push(item);}else{int res = 0;int num2 = Integer.parseInt(stack.pop());int num1 = Integer.parseInt(stack.pop());if(item.equals("*")){res = num1*num2;stack.push(""+res);}else if(item.equals("/")){res = num1/num2;stack.push(""+res);}else if(item.equals("+")){res = num1+num2;stack.push(""+res);}else if(item.equals("-")){res = num1-num2;stack.push(""+res);}else{throw new RuntimeException("运算符有误");}}}return Integer.parseInt(stack.pop());}
}
class Operation{public static int ADD = 1;//加public static int SUB = 1;//减public static int MUL = 2;//乘public static int DIV = 2;//除/*** 得到操作符的优先级，这里用的是自定义优先级* @param operation 操作符* @return*/public static int priority(String operation){int res = 0;switch (operation) {case "+":res = ADD;break;case "-":res = SUB;break;case "*":res = MUL;break;case "/":res = DIV;break;default:break;}return res;}
}

2.代码分析

代码主要分为两部分，中缀表达式转后缀表达式和计算函数

总结

这是一个栈的实际运用，前人太伟大，我们只能不断的学习和进步。