java - 将中缀转换为后缀表示法的程序

Question

这个问题已经有答案了:

Handling parenthesis while converting infix expressions to postfix expressions (2 个回答)

已关闭 6 年前。

我一直在做一项学校作业，要求我们将字符串从中缀表示法转换为后缀表示法。我们必须通过使用实现数组的堆栈来做到这一点。

这是我的实际转换类的代码:打包练习；

公开课练习{

public static  String infixToPostfix(String infix)
{

    Practice2 operatorStack = new Practice2();
    String output = "";
    char curChar;
    String input = infix;
    boolean isOperator=false;
    boolean empty=true;
    int curCharPrecedence=0;
    int topOfStackPrecedence=0;

    for(int i =0; i<input.length();i++){

        curChar = input.charAt(i);

        switch(curChar){
        case '+': isOperator=true;
        case '-': isOperator=true;
        case '/': isOperator=true;
        case '*': isOperator=true;
        case '(': isOperator=true;
        case ')': isOperator=true;
                    break;
        default: isOperator=false;
        }

        if(!isOperator){
            output=output+curChar;
        }

        else if(isOperator){
        output+=" ";

            if(empty){
                empty=false;
                operatorStack.Push(curChar);
            }


            else if(!operatorStack.empty()){
                switch(curChar){
                case ')': topOfStackPrecedence=0;
                case '+': curCharPrecedence=1;
                case '-': curCharPrecedence=1;
                case '/': curCharPrecedence=2;
                case '*': curCharPrecedence=2;
                case '(': topOfStackPrecedence=3;
                }

                switch((Character) operatorStack.peek()){
                case ')': topOfStackPrecedence=0;
                case '+': topOfStackPrecedence=1;
                case '-': topOfStackPrecedence=1;
                case '/': topOfStackPrecedence=2;
                case '*': topOfStackPrecedence=2;
                case '(': topOfStackPrecedence=3; 
                }


                if(curCharPrecedence>topOfStackPrecedence){
                    operatorStack.Push(curChar);

                }
                else{

                    while(!operatorStack.empty()&&topOfStackPrecedence>curCharPrecedence){


                        output+= operatorStack.pop();
                        output+=" ";

                        if(!operatorStack.empty())
                        switch((Character) operatorStack.peek()){
                        case ')': topOfStackPrecedence=0;
                        case '+': topOfStackPrecedence=1;
                        case '-': topOfStackPrecedence=1;
                        case '/': topOfStackPrecedence=2;
                        case '*': topOfStackPrecedence=2;
                        case '(': topOfStackPrecedence=3; 
                        }

                    }
                        operatorStack.Push(curChar);
                }





                }
            }

        }
    while(!operatorStack.empty()){
            output+=" ";
            output+= operatorStack.pop();
        }

    return output;
}

public static void main(String[] args)
{
   System.out.println(infixToPostfix("a+b*c"));
}

}

然后这是我的堆栈类代码:

package practice;

import java.util.EmptyStackException;



public class Practice2<T> extends Object{

public T[]  stack = (T[]) new Object[10];

    int topOfStack =-1;

    public Practice2()
    {
        stack = (T[]) new Object[10];
    }
    public Practice2(int capacity)
    {
        stack = (T[]) new Object[capacity];
    }

    public T Push(Object item)
    {
        if(topOfStack<=stack.length-1){
            T[] temporary = (T[]) new Object[stack.length];

            for(int i=0; i<stack.length-1;i++){
                temporary[i]=stack[i];

            }
            stack = (T[]) new Object[temporary.length+10];
            for(int i=0; i<temporary.length-1;i++){
                stack[i]=temporary[i];
            }

        }

        topOfStack++;
        stack[topOfStack]= (T) item;


        return (T) item;

    }

    public T peek()
    {

        return stack[topOfStack];


    }

    public T pop()
    {
        if(topOfStack==-1){
            throw new EmptyStackException();
        }
        else
            return stack[topOfStack--];

    }

    public boolean empty()
    {
        if(topOfStack==-1)
            return true;
        else
            return false;
    }

    public int size(){
        return topOfStack+1;
    }



}

每当我尝试运行此程序时，我都会收到以下错误消息:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at practice.Practice2.peek(Practice2.java:49)
    at practice.Practice.infixToPostfix(Practice.java:53)
    at practice.Practice.main(Practice.java:106

看来问题是我在堆栈类中的 peek 方法，但我不完全确定。

非常感谢任何帮助，我在这个程序上花了很多时间，并且非常需要其他人来看看它。

Answer 1

错误非常明显ArrayIndexOutOfBoundsException ....

原因在这里:

switch((Character) operatorStack.peek()){

您正在推送之前进行查看...更具体地说:您正在尝试获取位于 topOfStack =-1 的数组元素，这就是异常的原因。 ..