使用堆棧中綴到Postfix

Question

我不確定是否正確執行此操作。我試圖綴式轉化爲後綴式，如：

(3 + 4) * 2 

在後綴爲：

4 3 + 2 * 

我想如果可以做到這一切在一個方法。

現在我得到一個arrayoutofbounds錯誤，所以我彈出錯誤的地方或東西。

以下是infixtopostfix方法。

public void InfixToPostfix(String f) { 
    Stacked postfix = new Stacked(100); 
    Stacked op = new Stacked(100); 
    char c; 
    String fix = f; 
    //String out = ""; 
    int out = 0; 

    for (int i = 0; i < fix.length(); i++) { 
     c = fix.charAt(i); 

     if (c != '+' || c != '*' || c != '-' || c != '/' || c != '(' || c != ')') { 
      // out += c; 
      postfix.push(c); 
     } 
     else if (c == '+' || c == '*' || c == '-' || c == '/') { 
      if (c != ')') { 
       op.push(c); 
      } else { 
       out = (char) op.pop(); 
       s.push(out); 
      } 
      out = (char) op.pop(); 
      System.out.println("THE POSTFIX = " + out) 
     } 
    } 
} 

Answer 1

public class Postfix { 

    private int priority(char ch) { 
    if (ch == '^') 
    return 3; 
    if (ch == '/' || ch == '*') 
    return 2; 
    if (ch == '+' || ch == '-') 
    return 1; 
    return 0; 
    } 

    public String toPostfix(String in) { 

    String copy = in +")"; 
    Stack s = new Stack(copy.length()); 
    s.push('('); 

    int i, l = copy.length(); 
    char ch; 

    String r = ""; 
    for (i = 0; i < l; i++) { 

    ch = copy.charAt(i); 
    if (Character.isLetter(ch) == true) 
     r += ch; 

    else if (ch == '(') 
     s.push(ch); 

    else if (ch == ')') { 
     while (s.seeTop() != '(') 
     r += s.popSeeTop(); 

     s.pop(); 

    } else { 
     while (priority(ch) <= priority(s.seeTop())) 
     r += s.popSeeTop(); 

     s.push(ch); 
    } 
    } 
    return r; 
    } 
    } 

Answer 2

public class InfixToPostfix { 

Stack operatorStack = new Stack(); 

public String toPrefix(String expression) { 
    expression="("+expression+")"; 
    int i;  
    char token; 
    String output = ""; 
    for (i = 0; i < expression.length(); i++) { 
     token = expression.charAt(i); 
     if (Character.isLetterOrDigit(token) == true) 
      output += token; 
     else if (token == '(') 
      operatorStack.push(token); 
     else if (token == ')') { 
      char seeTop; 
      while ((seeTop = seeTop()) != '(') { 
       output += seeTop; 
       popSeeTop(); 
      } 

      operatorStack.pop(); 
     } else { 
      while (priority(token) <= priority(seeTop())) { 
       output += seeTop(); 
       popSeeTop(); 
      } 
      operatorStack.push(token); 
     } 
    } 
    return output; 

} 

private int priority(char operator) { 
    if (operator == '^') 
     return 3; 
    if (operator == '/' || operator == '*') 
     return 2; 
    if (operator == '+' || operator == '-') 
     return 1; 
    return 0; 
} 

private Character seeTop() { 
    if(!operatorStack.empty()) 
     return (Character) operatorStack.peek(); 
    else 
     return '0'; 
} 

private void popSeeTop() { 
    if(!operatorStack.empty()) 
     operatorStack.pop(); 
} 

Answer 3

/** 
* Convert arithmetic from infix to postfix 
* 
* @example 1 * (12 + 23) - (4/5) => 1 12 23 + * 4 5/- 
* @author Yong Su 
*/ 
import java.util.Stack; 
import java.lang.StringBuilder; 

class InfixToPostfix { 

    public static void main(String[] args) { 
     String infix = "1 * (12 + 23) - (4/5)"; 
     String postfix = convert(infix); 
     System.out.println(postfix); 
    } 

    /** 
    * Perform the conversion 
    * 
    * @param expression Arithmetic infix format 
    */ 
    public static String convert(String expression) { 
     // Use StringBuilder to append string is faster than 
     // String concatenation 
     StringBuilder sb = new StringBuilder(); 

     // Use a stack to track operations 
     Stack<Character> op = new Stack<Character>(); 

     // Convert expression string to char array 
     char[] chars = expression.toCharArray(); 

     // The length of expression character 
     int N = chars.length; 

     for (int i = 0; i < N; i++) { 
      char ch = chars[i]; 

      if (Character.isDigit(ch)) { 
       // Number, simply append to the result 
       while (Character.isDigit(chars[i])) { 
        sb.append(chars[i++]); 
       } 
       // Use space as delimiter 
       sb.append(' '); 
      } else if (ch == '(') { 
       // Left parenthesis, push to the stack 
       op.push(ch); 
      } else if (ch == ')') { 
       // Right parenthesis, pop and append to the result until meet the left parenthesis 
       while (op.peek() != '(') { 
        sb.append(op.pop()).append(' '); 
       } 
       // Don't forget to pop the left parenthesis out 
       op.pop(); 
      } else if (isOperator(ch)) { 
       // Operator, pop out all higher priority operators first and then push it to the stack 
       while (!op.isEmpty() && priority(op.peek()) >= priority(ch)) { 
        sb.append(op.pop()).append(' '); 
       } 
       op.push(ch); 
      } 
     } 

     // Finally pop out whatever left in the stack and append to the result 
     while(!op.isEmpty()) { 
      sb.append(op.pop()).append(' '); 
     } 

     return sb.toString(); 
    } 

    /** 
    * Check if a character is an operator 
    */ 
    private static boolean isOperator(char ch) { 
     return ch == '^' || ch == '*' || ch == '/' || ch == '+' || ch == '-'; 
    } 

    /** 
    * Define the operator priority 
    */ 
    private static int priority(char operator) { 
     switch (operator) { 
      case '^' : return 3; 
      case '*' : 
      case '/' : return 2; 
      case '+' : 
      case '-' : return 1; 
     } 
     return 0; 
    } 

} 

Answer 4

這裏有一個特別優雅和簡單的實現你想要做什麼，使用簡單Stacks

public class InfixToPostfix { 
    public static void main(String[] args) { 
     Stack<String> stack = new Stack<String>(); 
     while (!StdIn.isEmpty()) { 
      String s = StdIn.readString(); 
      if  (s.equals("+")) stack.push(s); 
      else if (s.equals("*")) stack.push(s); 
      else if (s.equals(")")) StdOut.print(stack.pop() + " "); 
      else if (s.equals("(")) StdOut.print(""); 
      else     StdOut.print(s + " "); 
     } 
     StdOut.println(); 
    } 
}