请用一个方法,java实现中缀表达式转成逆波兰式
时间: 2024-10-20 18:11:35 浏览: 9
在Java中,将中缀表达式转换成逆波兰式(也称为后缀表达式),可以使用栈的数据结构以及遍历表达式的操作。这里是一个简单的步骤说明:
1. 定义两个栈:一个用于存储操作数,另一个用于临时存储运算符。
2. 遍历输入的中缀表达式的每个字符:
- 如果遇到数字,直接压入操作数栈。
- 如果遇到左括号,将其压入运算符栈。
- 如果遇到右括号,从运算符栈弹出并依次压回操作数栈的操作数,直到遇到左括号为止。
- 如果遇到运算符,比较其优先级与当前运算符栈顶元素的优先级:
- 若当前运算符优先级低,或者为空,则直接将该运算符压入运算符栈。
- 否则,将栈顶的运算符及其对应的操作数压回操作数栈,然后处理当前运算符。
3. 当所有字符遍历完后,运算符栈中剩余的就是运算符,而操作数栈中就是逆波兰式的结果。
下面是一个简单的示例代码片段:
```java
import java.util.Stack;
public class infixToRPN {
private static final String[] operators = {"+", "-", "*", "/"}; // 运算符列表
public static String infixToRPN(String expression) {
Stack<Integer> opStack = new Stack<>(); // 运算符栈
Stack<String> rpnStack = new Stack<>(); // 逆波兰式栈
int i = 0;
while (i < expression.length()) {
char c = expression.charAt(i);
if (Character.isDigit(c)) {
// 添加数字到RPN栈
StringBuilder sb = new StringBuilder();
while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
sb.append(expression.charAt(i++));
}
rpnStack.push(sb.toString());
} else if (c == '(') {
opStack.push(i); // 保存左括号的位置
} else if (c == ')') {
while (!opStack.isEmpty() && opStack.peek() != '(') {
rpnStack.push(operators[opStack.pop()]);
}
opStack.pop(); // 弹出左括号
} else { // 遇到运算符
while (!opStack.isEmpty() && hasPrecedence(c, operators[opStack.peek()])) {
rpnStack.push(operators[opStack.pop()]);
}
opStack.push(i);
}
i++;
}
// 将剩余运算符推入RPN栈
while (!opStack.isEmpty()) {
rpnStack.push(operators[opStack.pop()]);
}
return rpnStack.toString();
}
private static boolean hasPrecedence(char op1, char op2) {
for (int i = 0; i < operators.length; i++) {
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) {
return true;
}
}
return false;
}
public static void main(String[] args) {
System.out.println(infixToRPN("(1 + 2) * 3 / 4")); // 输出:"1 2 + 3 * 4 /"
}
}
```
阅读全文