# Recursive Stack Evaluation

Page 1 of 1

## 2 Replies - 734 Views - Last Post: 03 April 2013 - 05:42 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=317546&amp;s=0c2ee0f79dc0cdae9ed53a6a580e5f9f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Cryptonomiconologist

Reputation: 0
• Posts: 6
• Joined: 14-March 13

# Recursive Stack Evaluation

Posted 03 April 2013 - 09:06 AM

Stack Evaluate RecursiveProblem

Hello,

Would someone be willing to take a look at this segment of code?
I am trying to figure out how this segment of code operates. I can see how the program can evaluate a simple prefix statement like + 7 6. I cannot see how the program can solve a statement like + + 7 6 + 5 4. I've inserted some print statements in order to see what the program is doing and it is showing
a = 7, b = 6, a = 13, a = 5, b = 4, b = 9, (22 = total). I cannot see
how a = 13, where is the first + symbol is stored, how b = 9. It seems like these three should be erased after being popped and then covered up by another 'popped = stack.pop();' statement. Where are these being stored?

Thank you,
Hank
```    /**
evaluate Prefix Stack, return int
*/
public static int evaluate(Stack<String> stack)
{
String popped = stack.pop();
if(!(popped.compareTo("+") == 0 || popped.compareTo("*")== 0))
{
int x = Integer.parseInt(popped);
return x;
}
else if(popped.compareTo("+") == 0)
{
int a = evaluate(stack);
System.out.println("a" + a);
int b = evaluate(stack);
System.out.println("b" + B)/>;
return a + b;
}
else
return 0;
}

```

Is This A Good Question/Topic? 0

## Replies To: Recursive Stack Evaluation

### #2 jon.kiparsky

• Pancakes!

Reputation: 8580
• Posts: 14,826
• Joined: 19-March 11

## Re: Recursive Stack Evaluation

Posted 03 April 2013 - 09:18 AM

If what you get off the stack is an integer, return it.

If not, if what you get off the stack is a +, then evaluate the next two items from the stack and add the result.

So to evaluate + + 7 6 + 5 4 requires three separate subprocesses, which I'll call a, b, and c

First a needs to do one evaluate which gets a "+" which means we call process b

b needs to do an evaluate which gets 7
and then another evaluate which gets a 6

b adds those and return the result (13) to the superior process (a)

Now a still needs another evaluate, which gets a +, so we go into process c

c needs an evaluate which gets 5 and then another evaluate which gets 4. Add and return 9

Now a has done two evaluate()s and got back two numbers, 13, and 9, so it can add those and return them.

Simple, no?

### #3 Cryptonomiconologist

Reputation: 0
• Posts: 6
• Joined: 14-March 13

## Re: Recursive Stack Evaluation

Posted 03 April 2013 - 05:42 PM

Great explanation, thank you.

C