最近在学习数据结构，看到“算数表达式的求值”这一小节中，有利用栈的后进先出（Last In First Out, LIFO）特性转换算数表达式的功能。我使用Java语言编写了一段代码用于将算数表达式的“中缀表示”转换为“后缀表示”的代码。
中缀表示是指运算符在两个操作数之（中）间的算数表达式表示方法，例如8/5；后缀表达式是指运算符在两个操作数之后的算数表达式表示方法，例如8 5/。在计算机硬件运算时，一般顺序扫描，此时使用后缀表达式较为快捷方便；例如8 5/4+表示先将8与5做除法，再与4相加，对计算机来说，它只需要顺序扫描即可，何时遭遇一个运算符，则弹出两个操作数进行计算，然后将结果入栈，再继续向前扫描。
中缀表示向后缀表示转换的方法为：不改变操作数顺序，按照优先级排序将操作符移动到操作数后方，删除界限符（括号）。
利用栈特性进行转换的具体步骤如下：
- 遇到操作数。直接输出
- 遇到运算符，需查看栈顶元素。
- 若栈顶元素是界限符（只能是左括号），则入栈
- 若栈顶元素是运算符，则查看两者优先级，若栈顶元素优先级低，则当前运算符入栈；若栈顶元素优先级更高，则将栈顶元素弹出输出。重复此步骤直至空栈或遭遇界限符或低优先级的操作符（即一直重复直至能将当前运算符压入栈）。
- 遇到界限符。若是左括号，则入栈；若是由括号，则弹出栈顶元素并输出，一直重复执行直至遇到左括号（左括号不输出）。
以下是我的代码（我只简单实现了加减乘除的转换）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
static int[] symbolPriority = new int[128]; // 符号优先级表，越小优先级越大
static {
symbolPriority['*'] = 1;
symbolPriority['/'] = 2;
symbolPriority['+'] = 3;
symbolPriority['-'] = 4;
symbolPriority['('] = 5; // 理论上说括号优先级更高，但在此处要将其作为一个界限，可以把它当作一个“分水岭”。可以理解为用于提升后面运算符的优先级
}
public static String middleExpress2SuffixExpress(String middleExpress) {
char[] me = middleExpress.toCharArray(); // 中缀表示的字符数组
StringBuilder sb = new StringBuilder(); // 存放后缀表示的字符串缓冲区
Stack<Character> symbols = new Stack<>(); // 存放运算符和界限符的栈
char temp = '\0'; // 临时变量，用于栈顶元素取出暂存
for(int i = 0; i < me.length; ++i) {
char symbol = me[i];
switch(symbol) {
case '+':
case '-':
case '*':
case '/':
sb.append(' '); // 数字后加个空格避免粘连
if(symbols.empty()) {
symbols.push(symbol); // 空栈直接压入
} else {
temp = symbols.peek();
if(symbolPriority[symbol] < symbolPriority[temp]) {
symbols.push(symbol); // 栈顶操作符优先级比当前低，直接入栈
} else {
while(true) { // 一直弹出栈内元素，直至遇到优先级比当前元素低的操作符或者界限符
sb.append(temp);
symbols.pop();
if(symbols.empty()) break;
temp = symbols.peek();
if(symbolPriority[symbol] < symbolPriority[temp]) break;
}
symbols.push(symbol); // 届时，将当前操作符入栈
}
}
break;
case '(':
symbols.push(symbol); // 界限符（左）直接入栈
break;
case ')':
// FIXME 没考虑表达式错误，这里默认有右括号就肯定能找到左括号
// 一直弹出栈，直至遭遇左界限符
while(!symbols.empty()) {
temp = symbols.pop();
if(temp == '(') break;
sb.append(temp);
}
break;
default:
if(Character.isWhitespace(symbol)) break; // 空格扔掉
sb.append(symbol);
}
}
while(!symbols.empty())
sb.append(symbols.pop()); // 表达式计算完后栈内操作符依次弹出
return sb.toString();
}
public static void main(String[] args) throws IOException {
System.out.println("输入中缀表示：");
try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
String middleExpress = null;
while(!(middleExpress = br.readLine()).isEmpty()) {
System.out.println(String.format("表达式的后缀表示为：%s", middleExpress2SuffixExpress( middleExpress)));
System.out.println("输入中缀表示（直接输入回车退出程序）：");
}
}
}
}
以下是我的测试输入及程序输出：
输入中缀表示：
8/5-4
表达式的后缀表示为：8 5 /4-
输入中缀表示（直接输入回车退出程序）：
28-9*(4+3)
表达式的后缀表示为：28 9 4 3+*-
输入中缀表示（直接输入回车退出程序）：
3*(x+y)/(2-x)
表达式的后缀表示为：3 x y+ *2 x-/
输入中缀表示（直接输入回车退出程序）：
(16+x)*(x*(x+y)+y)
表达式的后缀表示为：16 x+ x x y+ *y+*
输入中缀表示（直接输入回车退出程序）：
20+(16+9*4)/25-8
表达式的后缀表示为：20 16 9 4*+ 25 /+8-
输入中缀表示（直接输入回车退出程序）：
参考文献：
[1]李伟生.数据结构（第2版）[M].北京：中央广播电视大学出版社，2015：40-44.
