File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Evaluating infix expressions using generic stacks

 
Dan Mahoney
Greenhorn
Posts: 5
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am given the task to create a program that evaluates infix expressions using two generic stacks, one operator stack and one value stack.

This is my GenStack.java file:



and here is my implementation:



I'm having trouble with the eval and apply methods. The eval method doesn't appear to pickup ')' characters, like it doesn't even see them.

I've added a couple of printouts but I'm so lost and could use some guidance and insight. Any advice would be helpful.
 
William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13045
6
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Could the above be incrementing to point to the closing ) followed by your loop incrementing i past it.

Bill
 
Dan Mahoney
Greenhorn
Posts: 5
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This appears to be the case. How do I go about debugging that?
 
Tony Docherty
Bartender
Pie
Posts: 2878
59
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Get a pen and paper and write down the values of 'i' and 'token' before for loop starts. Now execute the code in your head and write down the new value of 'i' every time it changes. The really important part is when you have finished executing the while loop highlighted by William. 'i' is incremented in the while loop until token[i] is no longer 0-9, then what happens?
 
Dan Mahoney
Greenhorn
Posts: 5
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It pushes the string of tokens to the vals stack.

Correct me if I'm wrong, but can I decrement i by 1 after the push?
 
Tony Docherty
Bartender
Pie
Posts: 2878
59
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's one way of doing it, or you could use a second variable say 'j' as the index in the while loop and after the loop has finished add the length of the buffer-1 to 'i'.
 
Campbell Ritchie
Sheriff
Pie
Posts: 47258
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

The description of your pop() method is incorrect. It says throws an Exception but it never throws that Exception. Rather than messing about returning null, you should throw the ExceptionI suspect you will actually return the top but one value from your pop method.
Why have you called your method top() rather than peek() and why are you throwing a no such element exception? Shouildn't it throw an empty stack Exception? Since empty stack Exception is unchecked, you should describe it in the /** documentation comments */ rather than in a throws clause.
 
Winston Gutkowski
Bartender
Pie
Posts: 9477
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dan Mahoney wrote:I am given the task to create a program that evaluates infix expressions using two generic stacks, one operator stack and one value stack.

We seem to be getting a few questions about this recently. I wonder if you're all doing the same course?

And I'll say to you what I said to the others: What is the purpose of this program?
To write a generic Stack class, or to implement a shunting yard algorithm?

Even if it's both, my advice would be to separate the two problems completely.

And personally, if I was doing it, and the main purpose of the exercise is to write the SY bit, I'd write it using Java's own Stack class (java.util.Stack) first.

Once I know that it's working, I'd then tackle writing my own Stack class, using the same method names.
And when (and only when) I know that that's working, I'd substitute my class for java's and retest my SY.

It's called "problem isolation", and it really helps save you having to think about all sorts of different things at once.
Right now, every time you run into a problem, it's tough to know whether it's coming from your Project8 code or a bug in your GenStack class.

HIH

Winston

PS: Your code lines are far too long, which makes the Thread difficult to read.
I'd correct them myself, but you have TONS of them, so I suggest you do it yourself; it might help speed up answers.
 
Dan Mahoney
Greenhorn
Posts: 5
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Welcome to the Ranch

The description of your pop() method is incorrect. It says throws an Exception but it never throws that Exception. Rather than messing about returning null, you should throw the ExceptionI suspect you will actually return the top but one value from your pop method.
Why have you called your method top() rather than peek() and why are you throwing a no such element exception? Shouildn't it throw an empty stack Exception? Since empty stack Exception is unchecked, you should describe it in the /** documentation comments */ rather than in a throws clause.


Thanks for pointing this out. I have revised my code in this section:



The top method is named according to how my professor specified it be named. I am throwing an EmptyStackException now instead of NoSuchElementException:

 
Paweł Baczyński
Bartender
Pie
Posts: 1697
30
Firefox Browser IntelliJ IDE Java Windows
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:And personally, if I was doing it, and the main purpose of the exercise is to write the SY bit, I'd write it using Java's own Stack class (java.util.Stack) first.

Actually javadoc of java.util.Stack suggests:
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
Deque<Integer> stack = new ArrayDeque<Integer>();

So I'll listen to that suggestion ;).
 
Dan Mahoney
Greenhorn
Posts: 5
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've got it mostly working now as following the suggestions you all have provided but one of my given infix expressions is being evaluated to an incorrect answer.

String s ="3 - (4+5*6-77) / 4";

I get 11, but it should be 13.

Here is my algorithm.

 
Campbell Ritchie
Sheriff
Pie
Posts: 47258
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dan Mahoney wrote: . . . Thanks for pointing this out. I have revised my code . . .
You're welcome I think those alterations will sort out the problems.
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic