java - Java 中的 Shunting-Yard 算法实现给出了错误的输出和字符串索引超出范围？

Question

我正在实现 Shunting-Yard 算法并评估结果。这是一种基于引用的实现，使用节点(一个用于运算符，一个用于操作数)和堆栈(一个用于运算符，一个用于操作数)。

<小时/>

输入文件包含(仅前几行):

5
5-3
5*(3+4)
7*3+5*6
2+5*(7+8)/3

输出:

53 = 53
53513 = 1
535152
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: 
String index out of range: 7
    at java.lang.String.charAt(String.java:646)
    at LabIII.main(LabIII.java:48)

Process completed.

主要:

public class LabIII
{
public static String expr;
public static String line;

public static void main(String[] args) throws IOException
{       
    try
    {
        BufferedReader input = new BufferedReader(new FileReader("input.txt")); // Create input reader

        char token;
        int tokenI;
        char popOp;
        int popInt1;
        int popInt2;
        int result;

        while ((line = input.readLine()) != null) // While the input file still has a line with characters
        {
            operatorStack opStack = new operatorStack(); // Initalize the operator stack
            opStack.push(';');
            operandStack intStack = new operandStack();
            expr = line;
            int count = 1;

            while(count <= expr.length())
            {
                int index = count - 1;

                if(Character.isDigit(expr.charAt(index))) // If token is an operand
                {
                    tokenI = expr.charAt(index);
                    System.out.print(tokenI);
                    intStack.push(tokenI);
                    count++;
                }
                else
                {
                    token = expr.charAt(count);

                    if(token == ')')
                    {   
                        while(opStack.peek() != '(')
                        {
                            popOp = opStack.pop();
                            System.out.print(popOp);
                            popInt1 = intStack.pop();
                            popInt2 = intStack.pop();
                            result = evaluate(popInt1, popInt2, popOp);
                            intStack.push(result);                          
                        }
                        opStack.pop(); // Pop the "(" and discard it
                        count++;
                    }
                    else
                    {
                        while(inputPriority(token) <= stackPriority(opStack.peek()))
                        {
                            popOp = opStack.pop();
                            System.out.print(popOp);
                            popInt1 = intStack.pop();
                            popInt2 = intStack.pop();
                            result = evaluate(popInt1, popInt2, popOp);
                            intStack.push(result);
                        }
                        opStack.push(token);
                        count++;
                    }
                }
            }

            while (opStack.peek() != ';')
            {
                popOp = opStack.pop();
                System.out.print(popOp);
                popInt1 = intStack.pop();
                popInt2 = intStack.pop();
                result = evaluate(popInt1, popInt2, popOp);
                intStack.push(result);
            }

            System.out.print(" = " + intStack.pop());
            System.out.println();
            count = 0;              
        }
    }

    catch (IOException ex)
    {
        System.err.println("Exception:" + ex);
    }
}
}

operandStack(也是operatorStack的一个。相同，只是使用char而不是int):

public class operandStack
{
    int integ;
    NodeInt top;
    NodeInt temp;

    public operandStack() // Default constructor: empty stack
    {
        top = null;
    }

    public boolean isEmpty() // Returns true if the top of the stack is null
    {
        return top == null;
    }

    public void push(int integ) // Push an item onto the top of the stack
    {
        top = new NodeInt(integ, top);
    }

    public int pop()
    {
        NodeInt temp = top;
        top = top.getNext();
        return temp.getItem();
    }

    public void popAll()
    {
        top = null;
    }

    public int peek()
    {
        return top.getItem();
    }       
}

节点(也是操作数/整数的节点):

public class Node{

private char item;
private Node next;

public Node(char newItem)
{
    item = newItem;
    next = null;
}

public Node(char newItem, Node nextNode)
{
    item = newItem;
    next = nextNode;
}

public char getItem()
{
    return item;
}

public void setNext(Node nextNode)
{
    next = nextNode;
}

public Node getNext()
{
    return next;
}
}

算法如下:

初始化运算符堆栈以包含“;”(堆栈底部运算符)

获取第一个 token

当未到达表达式末尾时

如果标记是操作数，则

打印 token

将操作数压入操作数栈

否则，如果 token 是“)”，则

而操作符栈顶不等于‘(’

弹出操作符堆栈

打印运算符

将操作数堆栈弹出两次

对两个操作数应用指定的运算

将运算结果压入操作数栈

结束时

弹出“(”并将其丢弃

其他

当 inputPriority(token) ≤ stackPriority(操作符堆栈顶部)

弹出操作符堆栈

打印运算符

将操作数堆栈弹出两次

对两个操作数应用指定的运算

将运算结果压入操作数栈

结束时

将 token 压入操作符堆栈

获取下一个 token

结束时

而操作符栈顶不等于‘;’

弹出操作符堆栈

打印运算符

将操作数堆栈弹出两次

对两个操作数应用指定的运算

将运算结果压入操作数栈

结束时

弹出操作数栈并打印结果

感谢任何帮助。

Answer 1

token = expr.charAt(count);

这应该是

token = expr.charAt(index);

我不知道你为什么要费心去维护index和count。它只会导致这样的麻烦。