逆波兰表达式又叫后缀表达式，逆波兰表达式实现计算器求值，首先要把中缀表达式变成后缀表达式。先介绍一下前缀、中缀、后缀表达式。

一、前、中、后缀表达式

1.中缀表达式

中缀表达式就是我们常见的数学表达式，如：（3+40*6）*5-5
中缀表达式是我们人所熟悉的，人很容易就计算出来了，但是计算机不能够直接考虑到算数运算符的优先级关系，使用中缀表达式可能实现简单的计算工作（可参考这篇文章利用栈实现简单的计算器（加减乘除）），但是一旦涉及到了括号，计算机就不能够识别出优先级了。为了解决这个问题，研究人员就研究出了后缀表达式，后缀表达式能够使得计算机更简单的计算结果。

2.前缀表达式（波兰表达式）

前缀表达式又叫波兰表达式，前缀表达式的运算符位于操作数之前。
例如：

(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

中缀表达式转前缀表达式

1. 构造两个栈，s1,s2分别存储运算符与操作数
2. 从右至左扫描中缀表达式
   (1). 如果当前值为数值，读取，直到遇到运算符，将其转为一个数值并存入s2
   (2). 如果是运算符，则比较优先级
   a. 如果当前运算符的优先级大于等于s1栈顶运算符的优先级或s1栈空，则将运算符直接入栈；
   b.否则将栈顶运算符出栈并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级，再将当前运算符入栈。
   (3).如果是括号，则根据括号的方向进行处理。如果是右括号，则直接入栈；否则，遇左括号前将所有的运算符全部出栈并输出，遇右括号后将左右的两括号一起删除。
3. 重复上述操作2直至扫描结束，将栈内剩余运算符全部出栈并输出，再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。

3.后缀表达式（逆波兰表达式）

后缀表达式又叫逆波兰表达式，运算符位于操作数之后。
如：(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
再如：

中缀表达式转后缀表达式

1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2. 从左至右扫描中缀表达式；
3. 遇到操作数时，将其压s2；
4. 遇到运算符时，比较其与s1栈顶运算符的优先级：
   (1). 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
   (2). 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
   (3). 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
5. 遇到括号时：
   (1) 如果是左括号“(”，则直接压入s1
   (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6. 重复步骤2至5，直到表达式的最右边
7. 将s1中剩余的运算符依次弹出并压入s2
8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

如：1+（（2+3）*4）-5 转为后缀表达式的过程：

代码实现中缀表达式转后缀表达式：
先将中缀表达式转换成为对应的List，使用toInfixExpressionList方法，再见list转换为后缀表达式，使用parseSuffixExpression

private static final int ADD = 1; // +
private static final int SUB = 1; // -
private static final int MUL = 2; // *
private static final int DIV = 2; // //*** @Description: getLevelValue 获取运算符等级值*/
public static int getLevelValue(String operation){int res = 0;switch (operation){case "+":res = ADD;break;case "-":res = SUB;break;case "*":res = MUL;break;case "/":res = DIV;break;default:System.out.println(operation+"不是运算符");break;}return res;
}/*** @Description: toInfixExpressionList 将中缀表达式转换成对应的list*/
public static List<String> toInfixExpressionList(String s){ArrayList<String> stringArrayList = new ArrayList<>();int i = 0; // 指针，用于遍历中缀表达式的字符串String str;//多位数拼接char c;//每次遍历一个字符，存入cdo {c=s.charAt(i);if ((c < 48 || c >57) && c != '.' && c != ' '){  // 判断是不是运算符 ASCII 48~57对应数字0~9stringArrayList.add(""+c);i++;}else if(c == ' ') {i++;}else {str = ""; //重置strwhile ((i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) || c == '.'){str += c; //拼接i++;}stringArrayList.add(str);}}while (i < s.length());return stringArrayList;
}/*** @Description: parseSuffixExpression 转为后缀表达式*/
public static List<String> parseSuffixExpression(List<String> ls){Stack<String> s1 = new Stack<>(); // 符号栈// 说明： s2这个栈在整个转换过程中，灭有pop操作，后面需要逆序输出，比较麻烦，故使用List代替// Stack<String> s2 = new Stack<>(); // 存储中间结果栈ArrayList<String> s2 = new ArrayList<>();for (String item : ls) {if (item.matches(NUMREGEX)){ //如果是一个数字s2.add(item);}else if (item.equals("(")){ //如果是左括号“(”，则直接压入s1s1.push(item);}else if (item.equals(")")){// 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃while (!s1.peek().equals("(")){s2.add(s1.pop());}s1.pop();  // 将小括号弹出s1，消除小括号}else {// 若item优先级小于等于栈顶运算符的优先级，将s1栈的栈顶运算符弹出压入s2，再次与s1中的新栈顶运算符比较while (s1.size() != 0 && getLevelValue(s1.peek()) >= getLevelValue(item)){s2.add(s1.pop());}// item优先级大于栈顶运算符，压入s1s1.push(item);}}// 将s1 剩下的运算符弹出并加入s2while (s1.size() != 0){s2.add(s1.pop());}// 因为我们使用了List替代了栈，故顺序就是对应的逆波兰表达式，不需要逆序return s2;
}

二、逆波兰表达式计算

后缀表达式求值原理:
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。

例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:

1. 从左至右扫描，将3和4压入堆栈；
2. 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
3. 将5入栈；
4. 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
5. 将6入栈；
6. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

代码实现后缀表达式求值

/*** @Description: calculate 计算逆波兰表达式*/
public static double calculate(List<String> ls){Stack<Double> stack = new Stack<Double>();for (String item : ls) {if (item.matches(NUMREGEX)){// 入栈stack.push(Double.parseDouble(item));}else {// 注意出栈顺序double num2 = stack.pop();double num1 = stack.pop();double 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;}stack.push(res);}}return stack.pop(); // 返回结果
}

附逆波兰实现计算器完整代码：

public class PolandNotation {// 匹配数组public static final String NUMREGEX = "[1-9]\\d*\\.*\\d*";private static final int ADD = 1; // +private static final int SUB = 1; // -private static final int MUL = 2; // *private static final int DIV = 2; // //*** @Description: getLevelValue 获取运算符等级值*/public static int getLevelValue(String operation){int res = 0;switch (operation){case "+":res = ADD;break;case "-":res = SUB;break;case "*":res = MUL;break;case "/":res = DIV;break;default:System.out.println(operation+"不是运算符");break;}return res;}public static void main(String[] args) {String expression = "1 +((2+3)*4)-5";List<String> infixExpressionList = toInfixExpressionList(expression);System.out.println("strings.toString() = " + infixExpressionList.toString());List<String> suffixExpression = parseSuffixExpression(infixExpressionList);System.out.println("suffixExpression = " + suffixExpression);double calculate = calculate(suffixExpression);System.out.println("calculate = " + calculate);}/*** @Description: toInfixExpressionList 将中缀表达式转换成对应的list*/public static List<String> toInfixExpressionList(String s){ArrayList<String> stringArrayList = new ArrayList<>();int i = 0; // 指针，用于遍历中缀表达式的字符串String str;//多位数拼接char c;//每次遍历一个字符，存入cdo {c=s.charAt(i);if ((c < 48 || c >57) && c != '.' && c != ' '){  // 判断是不是运算符 ASCII 48~57对应数字0~9stringArrayList.add(""+c);i++;}else if(c == ' ') {i++;}else {str = ""; //重置strwhile ((i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) || c == '.'){str += c; //拼接i++;}stringArrayList.add(str);}}while (i < s.length());return stringArrayList;}/*** @Description: parseSuffixExpression 转为后缀表达式*/public static List<String> parseSuffixExpression(List<String> ls){Stack<String> s1 = new Stack<>(); // 符号栈// 说明： s2这个栈在整个转换过程中，灭有pop操作，后面需要逆序输出，比较麻烦，故使用List代替// Stack<String> s2 = new Stack<>(); // 存储中间结果栈ArrayList<String> s2 = new ArrayList<>();for (String item : ls) {if (item.matches(NUMREGEX)){ //如果是一个数字s2.add(item);}else if (item.equals("(")){ //如果是左括号“(”，则直接压入s1s1.push(item);}else if (item.equals(")")){// 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃while (!s1.peek().equals("(")){s2.add(s1.pop());}s1.pop();  // 将小括号弹出s1，消除小括号}else {// 若item优先级小于等于栈顶运算符的优先级，将s1栈的栈顶运算符弹出压入s2，再次与s1中的新栈顶运算符比较while (s1.size() != 0 && getLevelValue(s1.peek()) >= getLevelValue(item)){s2.add(s1.pop());}// item优先级大于栈顶运算符，压入s1s1.push(item);}}// 将s1 剩下的运算符弹出并加入s2while (s1.size() != 0){s2.add(s1.pop());}// 因为我们使用了List替代了栈，故顺序就是对应的逆波兰表达式，不需要逆序return s2;}/*** @Description: calculate 计算逆波兰表达式*/public static double calculate(List<String> ls){Stack<Double> stack = new Stack<Double>();for (String item : ls) {if (item.matches(NUMREGEX)){// 入栈stack.push(Double.parseDouble(item));}else {// 注意出栈顺序double num2 = stack.pop();double num1 = stack.pop();double 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;}stack.push(res);}}return stack.pop(); // 返回结果}}