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

問題は、提供している入力文字列です。スペースがあるため、ループの3回目の繰り返しでスペース文字が取得され、最後のelseステートメントに移動します。この時点でスタックは空であるため、 が得られStackEmptyExceptionます。((1+2)*3)入力文字列で試してください。

あなたのロジックでは、最後のelse実行時に少なくとも3つの要素（2桁と1つのオペランド）が必要です。

コードのもう 1 つの問題は、')' 閉じ中かっこが考慮されないため、入力"((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 に答える