0

我编写了一个代码，它从给定的字符串表达式创建一个二进制表达式树：

public ExprIF buildExpressionTree(String s)
{
    for(int i = 0; i<s.length(); i++)
    {
        if(Character.isDigit(s.charAt(i)) || isOperator(s.charAt(i)))//containOp(s,i))
        {
            treeRoot = new Expr(s.charAt(i)); 
            stack.push(treeRoot);
        }           
        else if(s.charAt(i) == '(')
        {
            //do nothing
        }   
        else
        {
            rightSubTree = stack.pop();
            treeRoot = stack.pop();
            leftSubTree = stack.pop();
            treeRoot.setLeft(leftSubTree);
            treeRoot.setRight(rightSubTree);
            stack.push(treeRoot);
        }           
    }
    return stack.pop();
}

当我在纸上测试它时，它运行良好。问题是这个错误：

Exception in thread "main" java.util.EmptyStackException
    at java.util.Stack.peek(Stack.java:102)
    at java.util.Stack.pop(Stack.java:84)
    at builder.TreeBuilder.buildExpressionTree(TreeBuilder.java:49)
    at builder.TreeBuilder.build(TreeBuilder.java:29)
    at Main.main(Main.java:12)

这个错误的原因是什么？

4

2 回答 2

0

对于您提供的输入，您的代码只是忘记处理空格。

解决方案1：添加以下代码以删除所有空格。

s = s.replaceAll("\\s", "");

解决方案2：更换

}

else
{
rightSubTree = stack.pop();
/* ... ... */

经过

} else if (c == ')'){
    rightSubTree = stack.pop();
    /* ... ... */
于 2013-04-23T14:35:39.730 回答
0

你的问题是你提供的输入字符串，它有空格，所以循环的第三次迭代得到一个空格字符并移动到最后一个else语句。此时堆栈为空，因此您得到StackEmptyException. 尝试使用((1+2)*3)输入字符串。

else在您的逻辑中，最后一次执行时您至少必须有 3 个元素（两位数和一个操作数） 。

代码中的另一个问题是不考虑')'右大括号，因此输入“((1+2)*3)” else语句将看到以下堆栈条目：

[1, +, 2]
[), *, 3]

您还需要跳过')'，最好编写一个检查跳过字符的方法：

private boolean skip(char c)
    {
        return c==')' || c=='(' || c==' ';
    }

现在在else if更改逻辑中：

else if(skip(s.charAt(i))
        {
            //do nothing, its a skip character
        }
于 2013-04-23T14:19:31.210 回答