一、前置知识
在学习中缀表达式转后缀表达式之前，需要先掌握以下几个概念。
1、中缀表达式：指运算符在中间位置的表达式，例如1+2。
2、前缀表达式：指运算符在前面位置的表达式，例如+12。
3、后缀表达式：指运算符在后面位置的表达式，例如12+。
4、运算符优先级：指不同运算符之间的优先级大小，例如乘法的优先级高于加法。
二、中缀表达式转后缀表达式的基本流程
1、从左到右扫描中缀表达式中的每一个数字或者运算符。
2、如果是数字，直接输出到后缀表达式中。
3、如果是左括号，进栈。
4、如果是右括号，将左括号上面的运算符全部弹出栈并输出到后缀表达式中，左右括号不输出。
5、如果是运算符，如果它的优先级比栈顶的运算符高，将它压入栈中。否则，将栈顶的运算符弹出，并输出到后缀表达式中，直到该运算符的优先级大于栈顶运算符的优先级为止。
6、重复步骤1~5，直到中缀表达式扫描完毕。
7、将栈内剩余的运算符依次弹出并输出到后缀表达式中。
三、代码实现
import java.util.Stack;
public class InfixToPostfix {
public static void main(String[] args) {
String infixExp = "(1+2)*3-4/5";
String postfixExp = infixToPostfix(infixExp);
System.out.println(postfixExp);
}
public static String infixToPostfix(String infixExp) {
Stack operatorStack = new Stack();
StringBuilder postfixExp = new StringBuilder();
for (char ch : infixExp.toCharArray()) {
if (ch >= '0' && ch <= '9') { // 判断数字
postfixExp.append(ch);
} else if (ch == '(') { // 左括号直接进栈
operatorStack.push(ch);
} else if (ch == ')') { // 右括号弹出栈内全部运算符
while (operatorStack.peek() != '(') {
postfixExp.append(operatorStack.pop());
}
operatorStack.pop(); // 弹出左括号
} else { // 运算符
while (!operatorStack.isEmpty() && operatorStack.peek() != '(' && priority(ch) <= priority(operatorStack.peek())) {
postfixExp.append(operatorStack.pop());
}
operatorStack.push(ch);
}
}
while (!operatorStack.isEmpty()) { // 栈内剩余的运算符全部输出
postfixExp.append(operatorStack.pop());
}
return postfixExp.toString();
}
private static int priority(char ch) { // 运算符优先级，数字越大，优先级越高
if (ch == '+' || ch == '-') {
return 1;
} else if (ch == '*' || ch == '/') {
return 2;
} else {
return 0; // 括号优先级最高
}
}
}
四、实例演示
例如，将中缀表达式“(1+2)*3-4/5”转换为后缀表达式如下：
1 2 + 3 * 4 5 / –
代码运行结果如下：
1+2 -> 12+ (1+2)*3 -> 12+3* 4/5 -> 45/ (1+2)*3-4/5 -> 12+3*45/- -> 12+3*4/5-
五、总结
中缀表达式转后缀表达式使用了栈的思想，通过将运算符依次压入和弹出栈来实现转换功能。在代码实现时，需要注意运算符优先级的大小以及左右括号的处理方式。
掌握了中缀表达式转后缀表达式的知识后，可以在实际编程中更加轻松地操作表达式的计算。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/227276.html
微信扫一扫 
支付宝扫一扫 