接尾

Question

へのJava RPN（逆ポーランド記法）中置私は無視されますが、ケースのように思われない例えば「（」スタックはPRNを構築し、ために使用されていることを、かなり確信しています：。

• 入力1： 52+（1 + 2）* 4-3
• 入力2： 52 +（+ 2（1）* 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）。すべての演算には結合重みがあり、+と - が最も低くなります。 2つのルールがあります。すぐに

• プリントアウト番号
• は
• 左括弧はあなたが左を打つまで
• 右括弧がスタックからポップスタックに行く重い項目に軽いアイテムを置くことはありません
  ：括弧は、その後、

はあなたの最初の例を考えると、左括弧、52+（1 + 2）* 4-3を削除し、ここにスタックであります以下の（あなたが持っていたものに近いアナログ）を使用してスイッチループの交換0

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. 

は、あなたの3例について、正しい答えを与えるだろう。実際のパーサーでは、各演算子に重みを与え、ポップメカニズムを一般化します。

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

ない具体的な質問が、私はアルゴリズムのこれらの種類を開発するためにお勧めしたい何かに正確な答え：テスト駆動devlopment（TDD）を見てみましょう。要約すると、infix2メソッドでは、テストパターン（式）を使用してメソッドを入力し、ifix2が正しい出力を生成するかどうかをテストするために、いくつかのユニットテスト（JUnitなど）を記述します。

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