Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite

I have written a code which creates a binary expression tree from a given string expression:

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();
}

When I test it on the paper, it works well. The problem is this error:

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)

What is the reason for this error?

share|improve this question
can you share sample input which you are using? – harsh Apr 23 at 14:07
"( ( 1 + 2 ) * 3 )" – Navid Koochooloo Apr 23 at 14:08
the operators are binary ones:*, +, -, /, ^, % this method returns it sees that the given character is equal one of these binary operators – Navid Koochooloo Apr 23 at 14:21

2 Answers

up vote 0 down vote

For the input you provided, your code simply forgot to deals with spaces.

Solution 1: add the following code to remove all spaces.

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

Solution 2: replace

}

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

by

} else if (c == ')'){
    rightSubTree = stack.pop();
    /* ... ... */
share|improve this answer
up vote 0 down vote

Your problem is input string you are providing, it has spaces so third iteration of loop gets a space character and moves to last else statement. At this time stack is empty hence you get StackEmptyException. Try with ((1+2)*3) input string.

In your logic you atleast have to have 3 elements (two digits and one operand) when last else is executed.

Another issue in your code is ')' closing braces are not considered so for input "((1+2)*3)" else statment will see following stack entries:

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

You need to skip ')' as well, its better to write a method which checks for skip characters:

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

Now in else if change logic: 

else if(skip(s.charAt(i))
        {
            //do nothing, its a skip character
        }
share|improve this answer
you are right, so I should have something like => else if(s.charAt(i) == '(' || s.charAt(i) == ' ') in my second else – Navid Koochooloo Apr 23 at 14:28
yes, but better to move character skipping logic in a separate method, see edited answer above. If it solves your problem you can accept the answer. – harsh Apr 25 at 6:10
Now my project is finished. But for testing, I've encountered another problem and that's when I get ( ( 1 + 2 ) * 3.5 ) => it gives me error of where I've got 3.5 => I know that the problem is reading character by character. can anyone help? – Navid Koochooloo Apr 29 at 23:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.