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

Convert Infix expression to prefix and postfix expression with Java

提问by Mohsen Bahman

I want to make an application to convert expression from infix mode to postfix and prefix mode.

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

For example:

例如：

infix : a+b*c

中缀：a+b*c

postfix: abc*+

后缀：abc*+

prefix : +a*bc

前缀：+a*bc

I want this by two classes, a class for postfix convert and an other class for prefix convert.

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

In addition I have written a class for stack like this :

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

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++;
}
}

I tried this code as postfix class :

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

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;
}
}

but this doesn't work with Parenthesis.

但这不适用于括号。

回答by Sergey Fedorov

All you need is:

所有你需要的是：

1. Split input expression to items, split items to multipliers.
2. Add to buffer parts and delimiters in the order you need

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

Some bad code to do it:

一些不好的代码来做到这一点：

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());
    }
}

Output:

输出：

abc*+
+a*bc