Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

# Evaluating Postfix Expression

Josh Theisen
Ranch Hand
Posts: 31
Hey everyone! First post here at The Ranch - been browsing for a while, but finally needed help with an assignment I'm working on.

Alrighty, here goes. We're supposed to input a String and have the program convert it from Infix to Postfix, and then evaluate the postfix expression.
The "convert" process working fine - it outputs the postfix value like it should. The problem comes when I need to evaluate it and give a result (i.e. 12+ will = 3).

I don't want to bore you guys with a whole bunch of code for you guys to work , so I"ll do my best to simplify it. Here's my basic thoughts of how the evaluate method will work:

As you can see, I declare a new character stack the size of the output so I have enough room. Next, I go through the output character by character and see if it's a value 0-9 (48-57 refer to the decimal value of the char).
If it's a number, it's pushed on to the stack. If not, it's an operator.

At this point, when I evaluate 12+, it gives me 99. I know that's partly due to the decimal value of the char, but I'm really stuck on how to do this.

Any suggestions for how to do this an easier way?

-Josh

Winston Gutkowski
Bartender
Posts: 10111
56
At this point, when I evaluate 12+, it gives me 99. I know that's partly due to the decimal value of the char, but I'm really stuck on how to do this.

It's not partly, it's entirely due to it. chars are not digits, and Java will never treat them as such.

Probably the simplest way to do what you want is to make your stack an int stack and store the numeric value of the character. The question is: how do you do that? You already know the decimal value, so how do you think you might convert 48 to 0, 49 to 1... and so on?

Winston

Josh Theisen
Ranch Hand
Posts: 31

I ended up make two classes called intStack and charStack to handle different parts of the program.

Here's the complete evaluate method -- it works from the little testing I've done... can't say I'm fond with how it's written, but it works right now. Any tips on how to clean it up?

Thanks all!

Josh Theisen
Ranch Hand
Posts: 31
Hm, no thoughts at all?

Winston Gutkowski
Bartender
Posts: 10111
56
Hm, no thoughts at all?

A few.
1. You could make all your if...else's a switch statement.
2. The code inside each if is identical except for the result so, instead of the above, why not create a result() method; maybe something like:
private static int result(char operator, int i1, int i2) {...
I leave you to work out the details.
3. Have you thought about how to handle negative numbers?
eg: "1-2+". Is that "-1 + 2" or "1 + -2", and how do you work it out?

Just a few from the top of my head.

Winston

Campbell Ritchie
Sheriff
Posts: 48442
56
• 1
I agree about the way it's wrritten, I am afraid.
You could use a switch-case on the operator, calling different methods.That is one way you can do it.

Ove Lindström
Ranch Hand
Posts: 326
Just a question: Does the assignment includes writing a stack or is it ok to use the Java Stack implementation (http://download.oracle.com/javase/6/docs/api/java/util/Stack.html)??

Winston Gutkowski
Bartender
Posts: 10111
56
I agree about the way it's wrritten, I am afraid.

No probs. Everyone has their own style. I just prefer to remove duplicate code whenever I see it, viz:but, as you say, there are many ways of doing it.

@OP: If you're not converting the character when you push it into the stack, you can do just as well with a char stack. I'd also be tempted to add a popAsDigit() method, viz:However, you have another, much more serious problem: What happens when you do "79+5-", and how do plan on getting around it?

Winston

Campbell Ritchie
Sheriff
Posts: 48442
56
Those 48 and 57 magic numbers are error-prone. There is a good reason for saying not to use numbers (except ±1 and 0) here. Your popAsDigit() method is much better.

If I remember correctly, that is an exercise from the Dragon Book, which specifically uses one-digit numbers. Pushing the int 16 back onto the stack will allow you to pop 16 later, still as an int.
as for built-in classes, the best stack is this, believe it or not. You can probably push and pop those values as ints. You would have to check the switch and find whether the chars +-*/ are being automatically cast to ints. Or more simply, if you use a stack of <Integer>, and it works, then the cast is working all right.

Winston Gutkowski
Bartender
Posts: 10111
56
If I remember correctly, that is an exercise from the Dragon Book, which specifically uses one-digit numbers. Pushing the int 16 back onto the stack will allow you to pop 16 later, still as an int.

Which is fine, as long as you only ever do one set of pushes and pops. As soon as you do more, 16 gets interpreted as an operator because it's not in the range 48 - 57 (or '0' to '9', whichever you prefer).

Winston

Josh Theisen
Ranch Hand
Posts: 31
Wow, thanks for all the replies - I'm almost not sure where to start

First thing, yes, I agree a switch statement would be much more useful here - I'll work on implementing that sometime when I get a chance.

Just a question: Does the assignment includes writing a stack or is it ok to use the Java Stack implementation (http://download.oracle.com/javase/6/docs/api/java/util/Stack.html)??

He wasn't clear with that, so I just wrote my own. I probably should have used the java implementation, but for this assignment I think I"ll levae how I've done it so far.

Those 48 and 57 magic numbers are error-prone.

This is where I'm uncomfortable. I really didn't want to write the method this way, but at the time I had no idea how to handle it.

I was trying to figure out if it was possible to do the evaluation with a 'char' stack, but I didn't see that working out since as far as I"m aware
a char can only handle one character at a time - i.e. what happens when I do 5+5 and I get 10? Can that be pushed as a single char?

Campbell Ritchie
Sheriff
Posts: 48442
56
• 1
Agree. But that depends what you are "pop"ping the 16 as. If you pop it as an int, it will be recognised as an operand.
• 7: stack now contains 7
• 9: Stack now 7 9
• +: Pop the two values, stack now empty. Add them and push the result. Stack = 16
• 5: Stack now 16 5
• - Pop the 5 and 16, subtract the two and push the result, so the stack is now 11.
• Note the way I had three pop operations in the code I posted earlier will handle that arithmetic incorrectly. So, as Winston Gutkowski hints, you would have to change and receive the operator, then pop two values, not three, from the stack.

Campbell Ritchie
Sheriff
Posts: 48442
56
As for 48 and 57, Winston Gutkowski has shown how you can subtract '0' from a char.
Yes, you can do arithmetic with chars. Try thisUnfortunately you won’t see much, since the char 10 (0x0a) is the line-feed character. So you will get a new line and nothing else. It may be easier to work with a stack of <Integer>. Note that auto-boxing can take the int 123 and convert it to the Integer representing 123, which makes life much easier when using Collections.
Of course, if you wrote your own stack, that is so much better.

Campbell Ritchie
Sheriff
Posts: 48442
56
Only noticed you are new today. Welcome

Winston Gutkowski
Bartender
Posts: 10111
56
Campbell Ritchie wrote:
• 5: Stack now 16 5
• - Pop the 5 and 16, subtract the two and push the result, so the stack is now 11.

• Oh yeah. Duh. For some reason I thought the ops were getting pushed onto the stack as well.

@Josh: Forget my rantings of the previous two posts. Campbell has it right, it should be an int stack; but you should convert before you push onto the stack, rather than when you pop it back out.

Winston

Josh Theisen
Ranch Hand
Posts: 31
Campbell Ritchie wrote:Only noticed you are new today. Welcome

Thanks! Definitely like the community here as opposed to other places I've been.

Am I even on the right track to go through the output character by character?

Forgive me, I'm definitely new to this kind of stuff.
From what I understand I should take the number (if I get one, as opposed to getting an operator), which is a char, convert it to an int
and then push it into the stack?
I think the whole thing between chars and ints and how to convert them is my biggest problem.

Thanks again, guys.

Winston Gutkowski
Bartender
Posts: 10111
56
Josh Theisen wrote:Am I even on the right track to go through the output character by character?
Sounds fine to me; except I think I would call it 'input' .
Forgive me, I'm definitely new to this kind of stuff.
No sweat. We all started in the same place.
From what I understand I should take the number (if I get one, as opposed to getting an operator), which is a char, convert it to an int and then push it into the stack?
Yup.
I think the whole thing between chars and ints and how to convert them is my biggest problem.
But you've got it now, yes?
All Campbell was saying is that it's better to use ch - '0' than ch - 48 for your conversion and ch >= '0' && ch <= '9' for your range check (more portable).
Thanks again, guys.
You're welcome.

Winston

Josh Theisen
Ranch Hand
Posts: 31
Winston Gutkowski wrote:But you've got it now, yes?
All Campbell was saying is that it's better to use ch - '0' than ch - 48 for your conversion and ch >= '0' && ch <= '9' for your range check (more portable).

Alright, got it.

I guess the only question I have now is how would I incorporate that range check into a switch statement?
My guess is that the below wouldn't work, but I'm unfamiliar with switches as well, so that's something I'll be learning too while I work on revising this evaluation.

Campbell Ritchie
Sheriff
Posts: 48442
56
You can't put a boolean expression after case like that. It is a case of if (c >= '0' && c <= '9') push c else operator(c) end.

Note I have changed from Java™ to Pseudocode half-way through that snippet.

Winston Gutkowski
Bartender
Posts: 10111
56
Josh Theisen wrote:I guess the only question I have now is how would I incorporate that range check into a switch statement? ...
Erm, no. Each case in a switch statement is a single value (except for default:), so they're not very good for ranges.
Great for your operators though, viz:and you could possibly put your range check in the default: block; although I still prefer a result() method (or indeed, a switch statement to calculate the result field).

BTW, don't forget the 'break's. Very important.

Winston

Josh Theisen
Ranch Hand
Posts: 31
EDIT:

Here's the complete code, re-visited, so to speak.

I definitely like this way better as of now, sure beats the old one. Any thoughts again?

Campbell Ritchie
Sheriff
Posts: 48442
56
• 1
Doesn't that look so much better Well done.

Josh Theisen
Ranch Hand
Posts: 31
Thanks to everyone who's helped. Much appreciated.

Winston Gutkowski
Bartender
Posts: 10111
56
• 2
Josh Theisen wrote:I definitely like this way better as of now, sure beats the old one. Any thoughts again?

Just one. You can remove the push() from the switch statement, viz:It's always my preference to include a default: block, even if it can theoretically never get executed, because code tends to change.
For example, if you added a new operator ('%' ?) and forgot to change the statement, the default acts as a failsafe. And in your case, it also acts as a "syntax" checker.

Another tiny little nitpicking point:does a calculation that isn't always used. An alternative would be:or indeedBut otherwise, it looks very good. Well done!

Winston

Josh Theisen
Ranch Hand
Posts: 31
EDIT: Winston, for your last couple of suggestions - is it possible for me to put the intChar inside the if loop? I was messing around with that, and then it hit me - the intChar isn't initialized yet so I can't compare whether or not it's >= 0 or <=9.

Rob Spoor
Sheriff
Posts: 20495
54
• 1
You'd either need to compare against '0' and '9' instead of 0 and 9, or declare intChar outside the if like you originally did.

Winston Gutkowski
Bartender
Posts: 10111
56
Josh Theisen wrote:EDIT: Winston, for your last couple of suggestions - is it possible for me to put the intChar inside the if loop? I was messing around with that, and then it hit me - the intChar isn't initialized yet so I can't compare whether or not it's >= 0 or <=9.

My apologies, I hadn't noticed that you'd changed your code there. My suggestion would be identical to Rob's, and you should disregard my faulty examples. The idea was right though .

Winston

Josh Theisen
Ranch Hand
Posts: 31
Awesome. Again, thanks for all the help/suggestions. I'm sure you'll see more of me in the future!

Campbell Ritchie
Sheriff
Posts: 48442
56
You’re welcome