我很确定,堆栈用于构建 PRN,'(' 被忽略,但情况似乎并非如此。例如:
- 输入 1:52+(1+2)*4-3
- 输入 2: 52+((1+2)*4)-3
- 输入3: (52+1+2)*4-3
输入 1 和输入 2 输出应该相同,输入 1 和输入 3 应该不同。
- 输出 1: 52 1 2 + 4 3 - * +
- 输出 2: 52 1 2 + 4 * 3 - +
- 输出 3: 52 1 2 + 4 3 - * +
public static String Infix2(String input) {
char[] in = input.toCharArray();
Stack<Character> stack = new Stack<Character>();
StringBuilder out = new StringBuilder();
for (int i = 0; i < in.length; i++)
switch (in[i]) {
case '+':
case '*':
case '-':
out.append(' ');
stack.push(in[i]);
break;
case ' ':
case '(':
break;
case ')':
out.append(' ');
out.append(stack.pop());
break;
default:
out.append(in[i]);
break;
}
while (!stack.isEmpty()) {
out.append(' ');
out.append(stack.pop());
}
return out.toString();
}
假设我希望输入 1 和 3 也能正常工作,我应该使用什么方法?
编辑: 在更改“+”、“-”、“*”和“/”后,对给定的输入有效。
public static String Infix2(String input) {
if (input == null)
return "";
char[] in = input.toCharArray();
Stack<Character> stack = new Stack<Character>();
StringBuilder out = new StringBuilder();
for (int i = 0; i < in.length; i++)
switch (in[i]) {
case '+':
case '-':
while (!stack.empty()
&& (stack.peek() == '*' || stack.peek() == '/'))
out.append(' ').append(stack.pop());
case '*':
case '/':
out.append(' ');
case '(':
stack.push(in[i]);
case ' ':
break;
case ')':
while (!stack.empty() && stack.peek() != '(')
out.append(' ').append(stack.pop());
if (!stack.empty())
stack.pop();
break;
default:
out.append(in[i]);
break;
}
while (!stack.isEmpty())
out.append(' ').append(stack.pop());
return out.toString();
}
最佳答案
算法非常简单(和 here is a good explanation )。每个操作都有一个绑定(bind)权重,+ 和 - 是最低的。有两条规则:
- 立即打印出数字
- 切勿将较轻的元素放在较重的元素上
- 左括号入栈
- 右括号从堆栈中弹出,直到您碰到左括号,然后删除左括号
给定你的第一个例子,52+(1+2)*4-3,这里是堆栈:
52+ => +
52+( => + (
52+(1+ => + ( +
52+(1+2) => + //right parentheses popped +
52+(1+2)*4 => + *
52+(1+2)*4-3 => + - //can't put - on top of *, so pop off *
... and then pop the stack until it's empty.
将您的开关循环替换为以下内容(与您所拥有的最接近的模拟)将为您的三个示例提供正确的答案。在真正的解析器中,您会给每个运算符一个权重并概括弹出机制。
for (int i = 0; i < in.length; i++)
switch (in[i]) {
case '+':
case '-':
while (!stack.empty() && (stack.peek() == '*' || stack.peek() == '/')) {
out.append(' ');
out.append(stack.pop());
}
out.append(' ');
stack.push(in[i]);
break;
case '*':
case '/':
out.append(' ');
stack.push(in[i]);
break;
case '(':
stack.push(in[i]);
break;
case ')':
while (!stack.empty() && stack.peek() != '(') {
out.append(' ');
out.append(stack.pop());
}
stack.pop();
break;
default:
out.append(in[i]);
break;
}
关于Java RPN (Reverse Polish Notation) 中缀到后缀,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1320891/