使用Java将Infix表达式转换为前缀和后缀表达式

Question

我想制作一个应用程序，将表达式从中缀模式转换为后缀和前缀模式。

例如：

中缀：a+b*c

后缀：abc*+

前缀：+a*bc

我想要两个类，一个用于后缀转换的类和另一个用于前缀转换的类。

此外，我还为堆栈编写了一个类，如下所示：

public class Stack {
int top = 0;
int stackSize = 0;
String[] stack;
public Stack(int stackSize){
    this.stackSize = stackSize;
    stack = new String[stackSize];
}
public int getTop(){
    return top;
}
public void push(String arg)throws Exception{
    if(top == stackSize){
        throw new Exception("Stack is full!");
    }
    else{
        this.stack[top++] = arg;
    }
}
public String pop()throws Exception{
    if(top == 0){
        throw new Exception("Stack is empty");
    }
    else{
        return this.stack[--top];
    }
}
public int stackCount(){
    return top++;
}
}

我尝试将此代码作为后缀类：

public class Postfix {
Stack stack = new Stack(1000);
char []operators = {'(','*','%','/','+','-',')'}; 
char[] infixExpression;
public Postfix(String infixExpression){
    this.infixExpression = infixExpression.toCharArray();
}
int priority(char operator){
    int result = 0;
    switch(operator){
    case '(':
        result = 1;
        break;
    case '*':
        result = 2;
        break;
    case '%':
        result = 3;
        break;
    case '/':
        result = 4;
        break;
    case '+':
        result = 5;
        break;
    case '-':
        result = 5;
        break;
    case ')':
        result = 7;
    }
    return result;
}
public String convertToPostfix(){
    int priority;
    String lastData;
    String exp = "";
    for(int i = 0;i<this.infixExpression.length;i++){
        priority = priority(this.infixExpression[i]);
        if(priority == 0){
            exp += this.infixExpression[i];
        }
        else if(priority == 1){
            try {
                stack.push(String.valueOf(this.infixExpression[i]));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        else if(priority == 7){
            while(stack.top != 0){
                try {
                    lastData = stack.pop();
                    if(!lastData.equals("(")){
                        exp += lastData;
                    }
                    else{
                        break;
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }
        else{
            try { 
                if(stack.top != 0){
                    while(true){
                        lastData = stack.pop();
                        stack.push(lastData);
                        if(stack.top == 0 || lastData.equals("(") || priority(lastData.toCharArray()[0]) > priority){
                            stack.push(String.valueOf(this.infixExpression[i]));
                            break;
                        }
                        exp += stack.pop();
                    }
                }else{
                    stack.push(String.valueOf(this.infixExpression[i]));
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
    if(stack.top != 0){
        try {
            while(stack.top != 0){
                exp += stack.pop();
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    return exp;
}
}

但这不适用于圆括号。

Answer 1

您只需要：

1. 将输入表达式拆分为项，将项拆分为乘数
2. 按需要的顺序添加到缓冲区的部分和分隔符

一些糟糕的代码：

public class Converter {
    private String infix;
    private void addMultPre(StringBuilder builder, String item) {
        String[] multipliers = item.split("[*/]");
        for (int j = 0; j < multipliers.length - 1; j++) {
            builder.append(infix.charAt(builder.length() + multipliers[j].length()));
            builder.append(multipliers[j]);
        }
        builder.append(multipliers[multipliers.length - 1]);
    }
    private void addMultPost(StringBuilder builder, String item) {
        String[] multipliers = item.split("[*/]");
        builder.append(multipliers[0]);
        for (int j = 1; j < multipliers.length; j++) {
            builder.append(multipliers[j]);
            builder.append(infix.charAt(builder.length()));
        }
    }
    public String prefix() {
        String[] items = infix.split("[+-]");
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < items.length - 1; i++) {
            builder.append(infix.charAt(builder.length() + items[i].length()));
            addMultPre(builder, items[i]);
        }
        addMultPre(builder, items[items.length - 1]);
        return builder.toString();
    }
    public String postfix() {
        String[] items = infix.split("[+-]");
        StringBuilder builder = new StringBuilder();
        char sign;
        addMultPost(builder, items[0]);
        for (int i = 1; i < items.length; i++) {
            sign = infix.charAt(builder.length());
            addMultPost(builder, items[i]);
            builder.append(sign);
        }
        return builder.toString();
    }
    public Converter(String infix) {
        this.infix = infix;
    }
    public static void main(String[] args) {
        Converter c = new Converter("a+b*c");
        System.out.println(c.postfix());
        System.out.println(c.prefix());
    }
}

输出：

abc*+
+a*bc