Java RPN（反向波兰表示法）中缀到后缀

我很确定，堆栈用于构建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 stack = new Stack(); 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 stack = new Stack(); 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(); } 

Answer 1

算法非常简单（ 这里有一个很好的解释 ）。 每个操作都有一个绑定权重，+和 – 是最低的。 有两个规则：

• 立即打印出数字
• 从不把较轻的物品放在较重的物品上
• 左括号进入堆栈
• 右括号从堆栈中弹出，直到您点击左括号，然后删除左括号

给出你的第一个例子，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; } 

Answer 2

不是具体问题的确切答案，而是我建议开发这些算法的东西：看一下测试驱动的开发（TDD）。 简而言之：为infix2方法编写几个unit testing – 例如使用JUnit – 如果infix2产生正确的输出，则使用测试模式（表达式）和测试来提供方法。

从简单的开始，比如

 assertequals("1", "1"); // positive number assertequals("-1", "-1"); // negative number assertequals("1+1", "1 1 +"); // simple addition assertequals(" 1 + 1 ", "1 1 +"); // simple addition with whitechars assertequals(" 1 + +1 ", "1 -1 +"); // simple addition with pos. number & whitechars assertequals(" 1 + -1 ", "1 -1 +"); // simple addition with neg. number & whitechars assertequals("(1+1)", "1 1 +"); // simple addition with brackets 

并且不要忘记非法表达

 String[] illegalExpressions = {null, "", " ", "1 +", "1 + 1)"}; 

你的例子的测试用例应该是

 assertequals("52+(1+2)*4-3", "52 1 2 + 4 * 3 -"); assertequals("52+((1+2)*4)-3", "52 1 2 + 4 * 3 -"); assertequals("(52+1+2)*4-3", "52 1 + 2 + 4 * 3 -");