概述
前缀、中缀、后缀表达式一般是根据操作符的位置来确定的，在我们去理解什么是前缀表达式和后缀表达式之前，可以先看下中缀表达式是什么？看如下的例子:
(3+4)* 5— 6 这就是我们正常一般看到的表达式。
虽然中缀表达式符合我们人的日常思维习惯，但是计算机在存储中缀表达式时，需要使用树这种数据结构(思考下，这里是因为包括括号的概念)，如果表达式过于复杂，那么树的高度会变得很高，大大增加了时间复杂度和空间复杂度。如果转换成线性结构，那么效率将变得高很多，所以需要将中缀表达式先转换成前缀或者后缀表达式，然后依靠栈这种线性数据结构来进行计算。一般计算机中存储基本是转成后缀表达式，然后来进行求值。
前缀表达式
前缀表达式又称为波兰表达式，他的特点是运算符位于操作数之前。
举例说明，(3+4) x 5 - 6 转为前缀表达式就是 - X + 3 4 5 6 .
中缀表达式如何转化成前缀表达式
*(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
* (2) 从右至左扫描中缀表达式；
* (3) 遇到操作数时，将其压入S2；
* (4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
* (4-1) 如果S1为空，则直接将此运算符入栈；
* (4-2) 否则，若优先级比栈顶运算符的较高或相等(后缀表达式中是较高,没有相等)或栈顶运算符为右括号“)”，
也将运算符压入S1；
* (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
* (5) 遇到括号时：
* (5-1) 如果是右括号“)”，则直接压入S1；
* (5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃
* (6) 重复步骤(2)至(5)，直到表达式的最左边；
* (7) 将S1中剩余的运算符依次弹出并压入S2；
* (8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
* (后缀表达式这里要将字符串反转输出,这里直接输出即可)
下面是进行转化的步骤:
这个是代码实现:
private static String zhong2Qian(String expression) {
//(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2;
Stack<Character> ops = new Stack<>();
Stack<Character> resultValues = new Stack<>();
//(2) 从右至左扫描中缀表达式;这里是先反转字符串再遍历其字符数组
expression = reverseString(expression);
char[] chars = expression.toCharArray();
for (char theChar : chars) {
//(3) 遇到操作数时，将其压入S2;
if (Character.isDigit(theChar))
resultValues.push(theChar);
//(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
else if (theChar == '+' || theChar == '-' || theChar == '*' || theChar == '/') {
dealTheChar(ops, resultValues, theChar);
}
//(5-1) 如果是右括号“)”，则直接压入S1；
else if (theChar == ')')
ops.push(theChar);
//(5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃;
else if (theChar == '(') {
char opsChar = ops.pop();
while (opsChar != (')')) {
resultValues.push(opsChar);
opsChar = ops.pop();
}
}
}
//(7)将S1中剩余的运算符依次弹出并压入S2；
while (!ops.empty()) {
resultValues.push(ops.pop());
}
//(8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
// (后缀表达式这里要将字符串反转输出,这里直接输出即可)
StringBuilder exp = new StringBuilder();
while (!resultValues.empty())
exp.append(resultValues.pop());
return exp.toString();
}
后缀表达式
后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作符之后，转化时时从左边往右扫描表达式的。这也是计算机中主要的存储算术表达式的方式。
中缀表达式如何转化成前缀表达式
/**
* 将中缀表达式转换为后缀表达式：
与转换为前缀表达式相似，遵循以下步骤：
* (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
* (2) 从左至右扫描中缀表达式；
* (3) 遇到操作数时，将其压入S2；
* (4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
* (4-1) 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
* (4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，
而这里则不包括相同的情况）；
* (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
* (5) 遇到括号时：
* (5-1) 如果是左括号“(”，则直接压入S1；
* (5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
* (6) 重复步骤(2)至(5)，直到表达式的最右边；
* (7) 将S1中剩余的运算符依次弹出并压入S2；
* (8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
* @return
*/
计算会比较复杂，所以这里用两个例子:
(1): 中缀表达式 1+((2 + 3) x 4)-5
结果为: 1 2 3 + 4 x + 5 -
(2): 中缀表达式 ( 3+ 4) x 5 -6
代码实现如下:
private static String zhong2hou(String expression) {
//(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
Stack<Character> ops = new Stack<>();
Stack<Character> resultValues = new Stack<>();
char[] chars = expression.toCharArray();
//(2) 从左至右扫描中缀表达式；
for (char theChar : chars){
//(3) 遇到操作数时，将其压入S2；
if (Character.isDigit(theChar))
resultValues.push(theChar);
//(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
else if (theChar == '+' || theChar == '-' || theChar == '*' || theChar == '/')
dealTheChar(ops,resultValues,theChar);
//(5) 遇到括号时：
//(5-1) 如果是左括号“(”，则直接压入S1；
else if (theChar == '(')
ops.push(theChar);
//(5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
else if (theChar == ')'){
char opsChar = ops.pop();
while (opsChar != '(') {
resultValues.push(opsChar);
opsChar = ops.pop();
}
}
}
//(7) 将S1中剩余的运算符依次弹出并压入S2；
while (!ops.isEmpty())
resultValues.push(ops.pop());
//(8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
StringBuilder exp = new StringBuilder();
while (!resultValues.empty())
exp.append(resultValues.pop());
return reverseString(exp.toString());
}
private static void dealTheChar(Stack<Character> ops, Stack<Character> resultValues, char theChar) {
//(4-1) 如果S1为空，则直接将此运算符入栈;
if (ops.empty()) {
ops.push(theChar);
return;
}
char popTheChar = ops.pop().charValue();
//(4-1) 如果S1为空，或栈顶运算符为右括号“(”，则直接将此运算符入栈;
//(4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）
if (popTheChar == '(' || getPriorityValue(theChar) > getPriorityValue(popTheChar)) {
ops.push(popTheChar);
ops.push(theChar);
}
//(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中
else {
resultValues.push(popTheChar);
//，再次转到(4-1)与S1中新的栈顶运算符相比较;
dealTheChar(ops, resultValues, theChar);
}
}
网友评论