Java的RPN（逆波兰式）中缀到后缀 [英] Java RPN (Reverse Polish Notation) infix to postfix
问题描述
我是pretty的肯定，栈用于构建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 - * +
公共静态字符串Infix2（字符串输入）{
的char []在= input.toCharArray（）;
堆叠＆LT;性格＆GT;堆栈=新的堆栈＆LT;性格＆GT;（）;
StringBuilder的出=新的StringBuilder（）;
的for（int i = 0; I＆LT; in.length;我++）
开关（在[I]）{
案+：
外壳 '*'：
外壳 '-'：
out.append（''）;
stack.push（在[I]）;
打破;
外壳 ' '：
外壳 '（'：
打破;
外壳 '）'：
out.append（''）;
out.append（stack.pop（））;
打破;
默认：
out.append（在[I]）;
打破;
}
而（！stack.isEmpty（））{
out.append（''）;
out.append（stack.pop（））;
}
返回out.toString（）;
}
假设我想输入1和3也上班，我应该用什么方法呢？
编辑： 修改完成后，+， - ，*和/工作了给定的输入
公共静态字符串Infix2（字符串输入）{
如果（输入== NULL）
返回 ;
的char []在= input.toCharArray（）;
堆叠＆LT;性格＆GT;堆栈=新的堆栈＆LT;性格＆GT;（）;
StringBuilder的出=新的StringBuilder（）;
的for（int i = 0; I＆LT; in.length;我++）
开关（在[I]）{
案+：
外壳 '-'：
而（！stack.empty（）
&&（stack.peek（）=='*'|| stack.peek（）=='/'））
out.append（''）.append（stack.pop（））;
外壳 '*'：
外壳 '/'：
out.append（''）;
外壳 '（'：
stack.push（在[I]）;
外壳 ' '：
打破;
外壳 '）'：
而（！stack.empty（）&& stack.peek（）！='（'）
out.append（''）.append（stack.pop（））;
如果（！stack.empty（））
stack.pop（）;
打破;
默认：
out.append（在[I]）;
打破;
}
而（！stack.isEmpty（））
out.append（''）.append（stack.pop（））;
返回out.toString（）;
}
该算法是pretty的简单（的这里是一个很好的解释）。每个操作都具有约束力的重量，用+和 - 是最低的。有两个规则：
- 在打印出来的数字立即
- 从来没有把一个打火机项目上更重的项目
- 在左括号进入堆叠
- 右键括号弹出堆栈，直到你打一个左括号，然后拆下左括号
鉴于你的第一个例子，52+（1 + 2）* 4-3，这里是堆栈：
52+ =＆GT; +
52+（= GT +（
52+（1+ =＆GT; +（+
52+（1 + 2）=＆GT; + //弹出右括号+
52+（1 + 2）* 4 =＆GT; + *
52+（1 + 2）* 4-3 =＆GT; + - //不能把 - 在*顶部，所以爆开*
...然后弹出堆栈，直到它是空的。
更换放置下面的开关回路（最接近模拟你有什么）会给你三个例子正确的答案。在实际的解析器，你会给每个运营商的重量和推广流行的机制。
的for（int i = 0; I＆LT; in.length;我++）
开关（在[I]）{
案+：
外壳 '-'：
而（stack.empty（）及！及（stack.peek（）=='*'|| stack.peek（）=='/'））{
out.append（''）;
out.append（stack.pop（））;
}
out.append（''）;
stack.push（在[I]）;
打破;
外壳 '*'：
外壳 '/'：
out.append（''）;
stack.push（在[I]）;
打破;
外壳 '（'：
stack.push（在[I]）;
打破;
外壳 '）'：
而（stack.empty（）及！＆安培; stack.peek（）='（'）{！
out.append（''）;
out.append（stack.pop（））;
}
stack.pop（）;
打破;
默认：
out.append（在[I]）;
打破;
}
I am pretty sure, that stacks are used for building PRN and '(' are ignored, but it does not seem to be the case. For example:
- input 1: 52+(1+2)*4-3
- input 2: 52+((1+2)*4)-3
- input 3: (52+1+2)*4-3
Input 1 and input 2 output should be the same, and input 1 and input 3 should differ.
- output 1: 52 1 2 + 4 3 - * +
- output 2: 52 1 2 + 4 * 3 - +
- output 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();
}
Assuming that i want input 1 and 3 also to work, what approach should i use?
edit: After the changes '+','-','*' and '/' worked for given inputs.
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();
}
The algorithm is pretty simple (and here is a good explanation). Every operation has a binding weight, with + and - being the lowest. There are two rules:
- print out numbers immediately
- never put a lighter item on a heavier item
- left parentheses go on the stack
- right parentheses pop off the stack until you hit a left parentheses, and then remove the left parentheses
Given your first example, 52+(1+2)*4-3, here is the stack:
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.
Replacing your switch loop with the following (closest analog to what you had) will give correct answers for your three examples. In a real parser you would give each operator a weight and generalize the pop mechanism.
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（逆波兰式）中缀到后缀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
