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 -");