スタック付きJavaインフィックス/ポストフィックスコンバータ

Question

私は次のコードで3つの関数を実装することになっています。

Functions: 
    1. evaluate arithmetic expression in postfix 
    2. convert arithmetic expression from infix to postfix 
    3. convert arithmetic expression from postfix to infix 

私はどこから始めればいいのか、どのように機能を見たり/作り上げる必要があるのか​​全く分かりません。あなたがこれらの3つの機能のうちの1つで私を助けることができれば、おそらく他の2つの機能を実行することができます。ここで

はコードです：ここでは

import java.util.Stack; 

public class Postfix { 

    public static int evalPostfix(String postfix) { 
     // TODO 
    } 

    public static String infixToPostfix(String infix) { 
     // TODO 
    } 

    public static String postfixToInfix(String postfix) { 
     // TODO 
    } 

    public static void main(String[] args) { 
     String infix1 = "(3-(7*2))"; 
     String postfix1 = "372*-"; 
     int eval1 = -11; 

     String infix2 = "((7+1)*((3-6)*(5-2)))"; 
     String postfix2 = "71+36-52-**"; 
     int eval2 = -72; 

     System.out.println("    postfix1: " + postfix1); 
     int n = evalPostfix(postfix1); 
     System.out.println("evalPostfix(postfix1): " + n); 
     if (n == eval1) { 
      System.out.println("      Right!"); 
     } else { 
      System.out.println("      Wrong!"); 
     } 
     System.out.println(); 

     System.out.println("    infix1: " + infix1); 
     String s = infixToPostfix(infix1); 
     System.out.println("infixToPostfix(infix1): " + s); 
     if (s.equals(postfix1)) { 
      System.out.println("      Right!"); 
     } else { 
      System.out.println("      Wrong!"); 
     } 
     System.out.println(); 

     System.out.println("    postfix1: " + postfix1); 
     s = postfixToInfix(postfix1); 
     System.out.println("postfixToInfix(postfix1): " + s); 
     if (s.equals(infix1)) { 
      System.out.println("      Right!"); 
     } else { 
      System.out.println("      Wrong!"); 
     } 
     System.out.println(); 

     System.out.println("    postfix2: " + postfix2); 
     n = evalPostfix(postfix2); 
     System.out.println("evalPostfix(postfix2): " + n); 
     if (n == eval2) { 
      System.out.println("      Right!"); 
     } else { 
      System.out.println("      Wrong!"); 
     } 
     System.out.println(); 

     System.out.println("    infix2: " + infix2); 
     s = infixToPostfix(infix2); 
     System.out.println("infixToPostfix(infix2): " + s); 
     if (s.equals(postfix2)) { 
      System.out.println("      Right!"); 
     } else { 
      System.out.println("      Wrong!"); 
     } 
     System.out.println(); 

     System.out.println("    postfix2: " + postfix2); 
     s = postfixToInfix(postfix2); 
     System.out.println("postfixToInfix(postfix2): " + s); 
     if (s.equals(infix2)) { 
      System.out.println("      Right!"); 
     } else { 
      System.out.println("      Wrong!"); 
     } 
     System.out.println(); 
    } 
} 

Answer 1

はあなたを助けるためにいくつかの不完全な擬似コードです：

function int evalPostfix(string postfix) 

    repeat 

    // Fetch the next item. 
    item <- get next item from postfix 

    // Process the current item. 
    if (item is operand) 
     push item onto stack 
    else if (item is operator) 
     pop required number of operands from the stack 
     push operator(operands) onto stack 
    else 
     throw error "Unrecognised item: " + item + " found." 
    end if 

    until (no more items in postfix) 

    return pop from stack 

end function 

あなたはあなたのコードが対処する必要がある各オペレータのために別々のオペレータ機能が必要になります。

Answer 2

これは古典的な 'スタック'データ構造の問題です。

あなたはすでにそれをスタック（あなたは、スタックのインポートを持っています。）との試みを与えていることが、あなたはまた、正規表現またはバイナリツリーなどでこれを解決することができ、

あなただけ解決するためのアイデアをしたい場合は、それは、これが役立つことを願って：スタックと接尾への変換

中置：

アルゴリズム：

1. スキャン左から右への入力中置式。
2. オペランドの場合は、一時的な文字列に追加します。
3. else演算子の優先順位がスタック内の演算子以上の場合、またはスタックが空の場合はスタックにプッシュします。
4. 「（」スタックすることを追加します。それ以外の
5. それがある場合、「）」がある場合は、ポップと「（」来る。
6. は2-5 utilの文字列をやり続けるまで、出力文字列に項目を追加複数の文字を持っている。

static Stack<String> stack; 

private static String doInfixToPostfix(String exp) { 
    stack = new Stack<String>(); 
    String output = ""; 
    for(int i=0;i<exp.length();i++){ 

     if(exp.charAt(i) == '('){ 
      stack.push("("); 
     } 
     else if(exp.charAt(i) == ')'){ 
      while(stack.size()>0 && stack.peek() != "("){ 
       output+= stack.pop(); 
      } 
      if(stack.size()>0 && stack.peek() != "(") 
       return "INVALID"; 
      else 
       stack.pop(); 
     } 
     else if(isOperand("" + exp.charAt(i))){ 
      //Its a Number 
      //It could be replaced to get more than one digits..... 
      output+= exp.charAt(i);; 
     } 
     else{ 
      //Its a operator 
      while(stack.size()>0 && (priority("" + exp.charAt(i)) < priority(stack.peek()))){ 
       output += stack.pop(); 
      } 
      stack.push("" + exp.charAt(i)); 
     } 
    } 
    while(stack.size()>0){ 
     output+=stack.pop(); 
    } 
    return output; 
} 


private static int priority(String value) { 
    if(value == "+" || value == "-") return 1; 
    else if(value == "*" || value == "/") return 2; 
    else if(value == "^") return 3; 

    return 0; 
} 

//This could be modified to accept more than one digits... 
private static boolean isOperand(String value) { 
    try{ 
     Integer.parseInt(value); 
    } 
    catch(NumberFormatException e){return false;} 
    return true; 
} 

とちょっと、代わりにそれらの非常に長いコードブロックで出力を比較、あなたは、単にのassertEquals（）テストケースを使用することもできます。