java 堆栈下溢

Question

我正在完成这项任务并在线程中不断收到异常 "main" java.lang.RuntimeException：Stack.pop(Postfix.java:74) 处的堆栈下溢在 Postfix.eval(Postfix.java:221) 在 Postfix.main(Postfix.java:112)

不知道为什么我查看堆栈并正确写入，我看不出为什么它在 (3*4)/5 时弹出

import java.io.IOException;
class  CharStack
{
    private final int STACKSIZE= 80;
    private int top;
    private char[] items;

    public CharStack(){
          items = new char[STACKSIZE];
          top =-1;

    }

    public boolean empty() {

        if(top==-1){
               return true;
           }


               return false;

    }

    public char pop() {
         if(empty()){
             throw new RuntimeException("Stack Underflow");
          }
     return items[top--];

    }

    public void push(char symb) 
    {
        if(top == STACKSIZE -1) {
            throw new RuntimeException("Stack Overflow");
       }
      items[++top] =symb;


    }

    public char peek() {
           if(empty()){
                throw new RuntimeException("Stack Underflow");
            }
           return items[top];
    }
    }
class Stack {
    private final int STACKSIZE= 80;
    private int top;
    private double[] items;

    public Stack(){
          items = new double[STACKSIZE];
          top =-1;

    }
    public void push(double x) 
    {
        if(top == STACKSIZE -1) {
               throw new RuntimeException("Stack Overflow");
          }
         items[++top] =x;



    }

    public double pop(){
        if(empty()){
             System.out.print(top);
            throw new RuntimeException("Stack Underflow");
         }
    return items[top--];

   }

    public double peek()  {
           if(empty()){

                throw new RuntimeException("Stack Underflow");
            }
           return items[top];


    }
   boolean empty()
   {
       if(top==-1){
           return true;
       }

           return false;


   }
}
public class Postfix {

     public final static int MAXCOLS = 80;

    public static void main(String[] args) throws IOException {

        String infix, pfix;
        System.out.println("Enter a infix  String: ");
        infix = readString().trim();
        System.out.println("The original infix expr is:  " + infix);
        pfix = postfix(infix);
        System.out.println("The Postfix expr is:  " + pfix);
        System.out.println("The value is :  " + eval(pfix));
    } // end main


    public static boolean isOperand(char x) 
    {
        if(x == '+')
        {
            return false;
        }
        else if(x == '-')
        {
            return false;
        }
        else if (x == '*')
        {
            return false;
        }
        else if (x ==  '/')
        {
            return false;
        }
        else if ( x== '$')
        {
            return false;
        }

        return true;

    }


    public static int operPrecedence(char oper) 
    {
        if(oper == '+'||oper == '-' )       
        {
            return 1;
        }

        else if (oper == '*' || oper ==  '/')
        {
            return 2;
        }

        else if (oper == '$')
        {
            return 3;
        }
        return 0;

    }


    public static boolean precedence(char top, char symb) 
    {

        if ((top != '('||top != ')')&&symb == '(')
        {
            return false;
        }
        if (top == '(' && (symb != '('||symb != ')') )
        {
            return false;
        }

        else if((top != '('||top != ')')&&symb ==')' )
        {
            return true;
        }
         int opcode1, opcode2;
         opcode1 =operPrecedence(top) ;
         opcode2 =operPrecedence(symb) ;

        if(opcode1>=opcode2){
            return true;
        }
            return false;

        }


    public static String readString() throws IOException {
        char[] charArray = new char[80];
        int position = 0;
        char c;
        while ((c = (char) System.in.read()) != '\n') {
            charArray[position++] = c;

        }
        return String.copyValueOf(charArray, 0, position); // turns a character array into a string, starting between zero and position-1

    }// end read string

    public static double eval(String infix) {

        char c;
        int position;
        double opnd1, opnd2, value;
        Stack opndstk = new Stack();
        for (position = 0; position < infix.length(); position++) {
            c = infix.charAt(position);
            if (Character.isDigit(c)) // operand-convert the character represent  of  
            // the digit into double and push it into the
            // stack
            {
                opndstk.push((double) Character.digit(c, 10));
            } else {

                // operator
                opnd2 = opndstk.pop();
                opnd1 = opndstk.pop();
                value = oper(c, opnd1, opnd2);
                opndstk.push(value);
            } // else
        } // end for
        return opndstk.pop();
    }// end eval

    public static String postfix(String infix) {
        int position, outpos = 0;
        char symb;
        char[] postr = new char[MAXCOLS];
        CharStack opstk = new CharStack();
        for (position = 0; position < infix.length(); position++) {
            symb = infix.charAt(position);
            if (isOperand(symb)) {
                postr[outpos++] = symb;
            } else {
                while (!opstk.empty() && precedence(opstk.peek(), symb)) {
                    postr[outpos++] = opstk.pop();
                } // end while
                if (symb != ')') {
                    opstk.push(symb);
                } else {
                    opstk.pop();
                }
            } // end else

        } // end for
        while (!opstk.empty()) {
            postr[outpos++] = opstk.pop();
        }
        return String.copyValueOf(postr, 0, outpos);

    }// end pos

    public static double oper(char symb, double op1, double op2) {

        double value = 0;
        switch (symb) {
            case '+':
                value = op1 + op2;
                break;
            case '-':
                value = op1 - op2;
                break;
            case '*':
                value = op1 * op2;
                break;
            case '/':
                value = op1 / op2;
                break;
            case '$':
                value = Math.pow(op1, op2);
                break;
            default:
                throw new RuntimeException("illegal operator: " + symb);

        }// end switch
        return value;
    }// end oper

}

Answer 1

至少您遇到的部分问题是您的 isOperand 方法。字符 ( 和 ) 不是操作数，但是，当它们传递给此方法时，它将 return true。为了进行快速测试，我在方法末尾添加了以下几行：

else if (x == '(')
{
    return true;
}
else if (x == ')')
{
    return true;
}

并且您的示例输入 (3*4)/5) 运行成功。但是，这会破坏您的后缀输出，因为它将括号从后缀版本中移除，而是打印 34*5/，我猜您不想要它。

然后，我查看了您的 eval 方法，根据我收到的错误消息，这就是问题所在：

Exception in thread "main" java.lang.RuntimeException: Stack Underflow
    at Stack.pop(Postfix.java:74)
    at Postfix.eval(Postfix.java:221)
    at Postfix.main(Postfix.java:112)

请注意行 Postfix.java:221，它指示调用产生错误的方法的行。如果您在调用该行之前输出字符 c，您会注意到 c 是 ( 字符，这意味着您的 eval 方法将 ( 识别为运算符，并试图在其后弹出两个操作数，导致下溢。

通过一些 System.out.println() 调用并查看您的错误，可以非常简单地确定所有这些。我会把实际修复留给你，但至少你现在有希望前进的方向。

java 堆栈下溢

java stack Underflow

java

stack

underflow