將表達式從前綴轉換爲後綴（面臨優先問題）

Question

我一直在試圖編寫一個將前綴表達式轉換爲後綴表達式的代碼。

到目前爲止，這裏是我做了（請注意，我是新的，因此可能不是有效！）

/*************************************************** 
NOTE: This code fails to realise the precedence 
    of parentheses and $ (exponential) expressions 
****************************************************/ 

import java.util.Scanner; 

class Stack{ 
    //Private Declarations 
    private int top; 
    private String a[] = new String [100]; 
    //Public Declarations 
    public Stack(){ 
     top = -1; 
     a[0] = "\0"; 
    } 
    public void push(String x){ 
     if (top != 99){ 
      a[++top] = x; 
     } 
     else{ 
      System.out.println("Stack overflow"); 
     } 
    }; 
    public String pop(){ 
     if (top == -1){ 
      System.out.println("\nStack empty!"); 
      return "\n"; 
     } 
     else{ 
      return a[top--]; 
     } 
    }; 
    public int ret_top(){ 
     return top; 
    }; 
} 


public class Prefix2Postfix { 
    public static void main(String[] args) { 
     //Declaration 
     Scanner in = new Scanner (System.in); 
     Stack op = new Stack(); 
     Stack sym = new Stack(); 
     char ch; 
     int i; 
     String exp, str, str1, str2, str3; 

     //Taking input from the user 
     System.out.println("Enter the prefix expression : "); 
     exp = in.next(); 

     for (i=0; i<exp.length(); i++){ 
      ch = exp.charAt(i); 
      if((ch == '+') 
      ||(ch == '-') 
      ||(ch == '*') 
      ||(ch == '/') 
      ||(ch == '$')){ 
       str = Character.toString(ch); 
       op.push(str); 
      } 
      else{ 
       str = Character.toString(ch); 
       sym.push(str); 
      if (sym.ret_top() == 1){ 
       str1 = sym.pop(); 
       str2 = sym.pop(); 
       str3 = op.pop(); 
       str1 = str2.concat(str1); 
       str1 = str1.concat(str3); 
       sym.push(str1); 
      } 
      } 
     } 

     //Output 
     str = sym.pop(); 
     System.out.println("After conversion to postfix" + ": " + str); 
     in.close(); 
    } 
} 

正如我在代碼中已經評論，我的代碼無法實現的優先級前綴表達式的情況。

例如：

Infix : a + (b*c) 
Prefix : +a*bc 
Postfix : abc*+ //Expected output 
Output I get : ab*c+ 

有什麼事在我使用或邏輯是有什麼我需要補充的嗎？ 你可以請建議一些方法，我的代碼可以正常工作？ 如果有人能幫助，我將不勝感激。

注：我們的教授建議我們編寫自己的堆棧類和代碼。另請注意，這是一項家庭作業。

在此先感謝。

---

編輯： 爲了確保我的籌碼正常工作我寫了下面的代碼和它的作品完全沒有問題。

import java.util.Scanner; 

class STACK { 
    //Private Declarations 
    private int top; 
    private int elem[] = new int [100]; 
    //Public Declarations 
    public STACK(){ 
     top = -1; 
     elem[0] = 0; 
    } 
    public void push(int x){ 
     if (top != 99){ 
      elem[++top] = x; 
     } 
     else{ 
      System.out.println("Stack overflow"); 
     } 
    }; 
    public int pop(){ 
     if (top == -1){ 
      System.out.println("Stack empty!"); 
      return 0; 
     } 
     else{ 
      return elem[top--]; 
     } 
    }; 
} 

public class StackPushPop { 
    public static void main(String[] args) { 
     STACK s = new STACK(); 
     Scanner in = new Scanner (System.in); 
     int choice, x; 
     do{ 
      System.out.println("Menu Options :"); 
      System.out.println("1 -> Push an element"); 
      System.out.println("2 -> Pop an element"); 
      System.out.println("3 -> Empty complete stack"); 
      System.out.println("Any other input for exit"); 
      System.out.println("Your choice : "); 
      choice = in.nextInt(); 
      switch(choice){ 
       case 1: 
        System.out.println("\nEnter element : "); 
        x = in.nextInt(); 
        s.push(x); 
        break; 
       case 2: 
        System.out.print("\nPopping element : "); 
        x = s.pop(); 
        if (x != 0){ 
         System.out.println(x); 
        } 
        break; 
       case 3: 
        System.out.println("\nEmptying stack!"); 
        x = 1; 
        while (x!= 0){ 
         x = s.pop(); 
         if(x != 0){ 
          System.out.print(x + " "); 
         } 
        } 
        break; 
       default: 
        choice = 0; 
      } 

     }while (choice != 0); 
    } 
} 

---

編輯 我終於成功地創建一個程序，工作完全正常。

import java.util.Scanner; 

class STACK{ 
    private int top, MAX; 
    private String a[] = new String [1000]; 
    public STACK(){ 
     top = -1; 
     MAX = 1000; 
     a[0] = ""; 
    } 
    public void push(String x){ 
     if (top <= MAX-1){ 
      a[++top] = x; 
     } 
     else{ 
      System.out.println("Stack overflow"); 
     } 
    }; 
    public String pop(){ 
     if (top == -1){ 
      System.out.println("\nStack empty!"); 
      return "\n"; 
     } 
     else{ 
      return a[top--]; 
     } 
    }; 
    public int getTop(){ 
     return top; 
    }; 
} 

public class Prefix2Postfix_STACK{ 
    static boolean isOperator (char ch){ 
     switch (ch){ 
      case '+': 
      case '-': 
      case '*': 
      case '/': 
      case '$': 
         return true; 
      default : 
         return false; 
     } 
    } 
    public static void main(String[] args) { 
     //declarations 
     Scanner in = new Scanner (System.in); 
     String exp; 
     int i; 
     STACK s = new STACK(); 
     String exp_str[] = new String[100]; 
     String postfix_exp = "\n"; 

     //input 
     System.out.println("Enter prefix expression (No spaces or brackets) : "); 
     exp = in.next(); 

     //create a string array of all characters but in reverse 
     for(i=0; i<=exp.length()-1; i++){ 
      exp_str[exp.length()-1-i]=Character.toString(exp.charAt(i)); 
     } 

     //computing postfix: 
     i=0; 
     do{ 
      if (!isOperator(exp_str[i].charAt(0))) 
       s.push(exp_str[i]); 
      else{ 
       String str1 = s.pop(); 
       String str2 = s.pop(); 
       str1 = str1 + str2 + exp_str[i]; 
       postfix_exp = str1; 
       s.push(str1); 
      } 
      i++; 
     }while(s.getTop()>=0 && i!=exp.length()); 

     //Output 
     System.out.println("After converting to postfix : " + postfix_exp); 
     in.close(); 
    } 
} 

Answer 1

您所寫的代碼只是將操作員從左向右移動的工作。 在正確的方向輕推：

插入一個條件在 前綴字符串檢查符號之間的運營商和先解決他們！

這可能會解決您的問題。