Java的RPN（逆波兰式）缀与postfix

Question

我敢肯定，这堆被用于建筑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(); 
} 

Answer 1

算法很简单（和here is a good explanation）。每个操作都有约束力，+和 - 是最低的。有两个规则：

• 打印出来的数字立即
• 从来没有把一个打火机项目上更重的项目
• 左括号进入堆叠
• 右括号弹出堆栈，直到你击中左括号，然后拆下左括号

鉴于你第一示例中，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方法编写几个单元测试（例如使用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 -");