parsing prefix expression small bug?

hello there! i have created this parser in java which reads expressions in the form of ( + 4 4 ) and
( + ( + 4 4 ) 4 ) it reads them and gives the correct result but it doesnt give me the correct result for expressions like these:

( + 4 ( + 4 4 ) )

which are just a minor variation. it gives me 16 instead of 12 when i try and parse this type of expression. it probably adds an extra 4 somewhere but i cant find where. could someone try to help me fix it. heres the code that takes the expression as a String and evaluates it (please note that im keeping it simple only number 4 and + operators are allowed)

the psuedo version:

calc():
while not the end of the expression
read in a token
if the token is an operator, push it on the ops stack
else if it is a number, push it on the values stack
else if it is an open paren,
calc() the sub-expression recursively
else if it is a close paren,
pop the current function of the ops stack
check how many arguments the op takes, and
pop that many values off of the values stack
calculate the result of the op and push it on the stack
return
else
print an error message and exit (or throw an exception, your choice, though this is not quite an exceptional thing)

my code converted from the psuedo version:

Code:

---

public int evaluate(String exp) {
        int result = 0;
        String[] expr = exp.split(" ");
        int i = 0;
        while (i <= expr.length -1) {
            String token = expr[i];
 
            if (token.equals("+")) {
                opStack.push(expr[i]);
            } else if (token.equals("4")) {
                valueStack.push(expr[i]);
            } else if (token.equals("(")) {
             
                ArrayList<String> res2  = new ArrayList<String>();
                ArrayList<String> arr= new ArrayList<String>();
               
                String newExpr = "";
                for (String s : expr) {
                    arr.add(s);
                }
                res2.addAll(arr.subList(i+1, arr.size() -1));
                for (String a : res2) {
                    newExpr = newExpr + a + " ";
 
                }
                evaluate(newExpr);
            } else if (token.equals(")")) {
                String op = (String) opStack.pop();
                int n1 = Integer.parseInt((String) valueStack.pop());
                int n2 = Integer.parseInt((String) valueStack.pop());
                result = n1 + n2;
                valueStack.push("" + result);
 
            } else {
                System.err.println("Invalid Expression!");
            }
            i++;
 
        }
        return result;
 
    }

---

t basically doesnt calculate expressions which have a number after the operator AND and an open bracket. e.g.

( + 4 ( + 4 4 ) )

any ideas?? thanks guys!

I'm not sure how you're seeing those results. I took your code as is and am getting 8 for both of your examples
+ ( + 4 4 ) 4
and
+ 4 ( + 4 4 )

Looks like you've got some refining to do.

Quote:

---

Originally Posted by gitter1226

I'm not sure how you're seeing those results. I took your code as is and am getting 8 for both of your examples
+ ( + 4 4 ) 4
and
+ 4 ( + 4 4 )

Looks like you've got some refining to do.

---

replace this line res2.addAll(arr.subList(i+1, arr.size() -1));

with this:

res2.addAll(arr.subList(i+1, arr.size()-i ));


the thing is now it doesnt work for expression like ( + ( + 4 4 ) ( + 4 4 ) )

The problem you've got is a logic problem with the parser. Forget writing Java code for a while, and go back to the design. Work out how to parse and evaluate the expressions step by step on paper. Take the place of the computer and use your problem examples to test your design by stepping through, writing down the results and intermediate values as you go. When you can successfully step through all your problem input, it should be simple to translate your design into Java. At present, it looks like the Java code you already have is confusing the issue. By tweaking what you've got, you might fix it in five minutes, but if the basic design is flawed it might take days. Once you have a working design, you can rework your existing code, but don't try to fix the design in the code.

The value of a prototype is in the education it gives you, not in the code itself...
A. Cooper

aaah thats very wise... ill try that thank you! :)