0

我正在实现 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);
    }
}
}

操作数堆栈（也是运算符堆栈之一。相同，只是使用 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;
}
}

算法如下：

初始化运算符堆栈以包含“;” （堆栈运算符的底部）

获取第一个令牌

虽然没有到达表达式的结尾

如果令牌是操作数，那么

打印令牌

将操作数压入操作数堆栈

否则，如果令牌是 ')' 那么

而运算符栈顶不等于'('</p>

弹出操作符堆栈

打印运算符

弹出操作数堆栈两次

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

将运算结果压入操作数栈

结束时

弹出“（”并丢弃它

别的

而 inputPriority(token) ≤ stackPriority(操作栈顶)

弹出操作符堆栈

打印运算符

弹出操作数堆栈两次

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

将运算结果压入操作数栈

结束时

将令牌推入操作员堆栈

获取下一个令牌

结束时

而运算符栈顶不等于';'</p>

弹出操作符堆栈

打印运算符

弹出操作数堆栈两次

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

将运算结果压入操作数栈

结束时

弹出操作数堆栈并打印结果

任何帮助表示赞赏。

4

2 回答 2

2 
token = expr.charAt(count);

这应该是

token = expr.charAt(index);

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

于 2015-04-01T00:04:06.403 回答
1

我弄清楚了这些问题。还有另外两个问题：

首先，输入文件末尾有两个额外的空行，导致异常。

其次，tokenI = expr.charAt(index)将 ASCII 值分配给 tokenI（例如，输入值 5 导致 tokenI 为 53），因此我只需减去 48（0 的 ASCII 值）即可解决问题。tokenI = expr.charAt(index) - 48在那之后，其他一切都到位了。

另外，正如@EJP 所说，“index”和“count”变量都不需要，所以我删除了“count”，只使用了“index”。

于 2015-04-01T01:31:41.467 回答