将表达式从前缀转换为后缀(面临优先级问题)

Question

我一直在尝试编写一段代码，将Prefix表达式转换为Postfix表达式。

到目前为止，以下是我所做的（注意，我是新手，因此可能效率不高！）

/***************************************************
 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] = "";
    }
    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+

我使用的逻辑有问题吗？或者我需要补充什么？你能建议一些方法让我的代码正常工作吗？如果有人能帮忙，我将不胜感激。

注意：我们的教授建议我们编写自己的堆栈类和代码。请注意，这是一项家庭作业。

提前谢谢。

---

编辑：为了确保我的STACK工作良好，我写了下面的一段代码，它工作得很好。

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

您编写的代码只完成将运算符从左向右移动的工作。向右推动：

在中的符号之间插入一个条件以检查运算符前缀字符串并首先解决它们！

这可能会解决你的问题。