It's not a secret anymore!*
The moose likes Beginning Java and the fly likes Evaluating Postfix Expression Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of JavaScript Promises Essentials this week in the JavaScript forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Evaluating Postfix Expression" Watch "Evaluating Postfix Expression" New topic
Author

Evaluating Postfix Expression

Josh Theisen
Ranch Hand

Joined: Sep 23, 2011
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?

Thanks everyone in advance!
-Josh
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8176
    
  23

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?

Have a thunk about it.

Winston
Josh Theisen
Ranch Hand

Joined: Sep 23, 2011
Posts: 31
Thanks for the reply.

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

Joined: Sep 23, 2011
Posts: 31
Hm, no thoughts at all?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8176
    
  23

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

Joined: Oct 13, 2005
Posts: 39773
    
  28
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

Joined: Mar 10, 2008
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

Joined: Mar 17, 2011
Posts: 8176
    
  23

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

Joined: Oct 13, 2005
Posts: 39773
    
  28
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

Joined: Mar 17, 2011
Posts: 8176
    
  23

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

Joined: Sep 23, 2011
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

Joined: Oct 13, 2005
Posts: 39773
    
  28
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

    Joined: Oct 13, 2005
    Posts: 39773
        
      28
    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

    Joined: Oct 13, 2005
    Posts: 39773
        
      28
    Only noticed you are new today. Welcome
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 8176
        
      23

    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

    Joined: Sep 23, 2011
    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

    Joined: Mar 17, 2011
    Posts: 8176
        
      23

    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

    Joined: Sep 23, 2011
    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

    Joined: Oct 13, 2005
    Posts: 39773
        
      28
    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

    Joined: Mar 17, 2011
    Posts: 8176
        
      23

    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

    Joined: Sep 23, 2011
    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

    Joined: Oct 13, 2005
    Posts: 39773
        
      28
    Doesn't that look so much better Well done.
    Josh Theisen
    Ranch Hand

    Joined: Sep 23, 2011
    Posts: 31
    Thanks to everyone who's helped. Much appreciated.
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 8176
        
      23

    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

    Joined: Sep 23, 2011
    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

    Joined: Oct 27, 2005
    Posts: 19755
        
      20

    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.


    SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
    How To Ask Questions How To Answer Questions
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 8176
        
      23

    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

    Joined: Sep 23, 2011
    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

    Joined: Oct 13, 2005
    Posts: 39773
        
      28
    You’re welcome
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Evaluating Postfix Expression