• Post Reply Bookmark Topic Watch Topic
  • New Topic

stack implementation using a linked list for reverse polish notation  RSS feed

 
phi tran
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi everyone!

I have an assignment that I need some help with. We have to create our own stack data structure using a linked list (can't use Java's linked list either). With the stack we have to create a Reverse Polish Notation calculator (+, -, *, / only). I am stuck on how to iterate through the stack to check for operands. When testing my stackCount() method in the ReversePolish class the method is reading the count as zero BUT the count method works perfectly when calling it from the stack (i hope that made sense). the iterateStack() method in the ReversePolish class is suppose to go through the stack to look for operands and operators and perform the necessary operations ( at least i think that's how i need to do it).

Once again thanks for taking the time to read this and help.

Below is a copy of my classes:

main class


node class


singly linked list class


stack class


reverse polish class
 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I suggest your node class belongs entirely to the list class and should therefore be an inner class there. And similarly, the list class should probably be a private inner class of the stack class. A stack is not a list and should therefore not extend the list class.
Your methods in the stack class should be named push pop peek and depth. The pop and peek methods must not have void return type, but return the top value on the stack. The list class (or the stack class) should keep a depth field; every time you push or pop it changes by 1.

Make your classes parameterised. Call it Stack<T> and LinkedList<T> and Node<T> and in each case call the type of the variable T throughout. If you are using the stack for Strings you pass String
Stack<String> myStack = new Stack<>();
 
Stephan van Hulst
Saloon Keeper
Posts: 7973
143
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The entire point of reverse polish notation is that you don't have to iterate the stack. Whenever you encounter an operator, you just pop two operands, and push the result of applying the operator to them.
 
Gordon Brown
Ranch Hand
Posts: 58
2
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have a few suggestions, but the most important point is the one Stephan has already made: you do not want to iterate the stack.

Firstly, unless you have been explicitly told to name it as such, "Program1" is a terrible name for a class. There's actually no need to have separate class just to kick off the program, in my opinion: Stick the main method in your ReversePolish class. (A better name might be RPNCalculator.)

How about defining an interface for a Stack, and having another class, LinkedStack, that implements that interface? That way you can code against an interface rather than an implementation. (As Campbell suggested, you should make these generic types: e.g. Stack<E>. If you haven't covered generics yet, though, don't worry about using type parameters.) For bonus points, list the pre- and post-conditions, return types (and, if you're comfortable with them, exceptions) for each of the interface methods. Doing this will help you better understand Stack's methods, and why they should have the return types they do. e.g. for push(E obj), you could have:

Preconditions:
  • stack is not empty

  • postconditions:
  • stack size is decreased by 1
  • top item of stack is returned
  • the rest of the stack is unchanged

  • returns the element on the top of the stack
    throws StackException if stack is empty


    LinkedStack then implements Stack (or, if using generics: LinkedStack<E> implements Stack<E>), and should have a private member variable of type Node (or Node<E>), representing the top of the stack (thus you could call it top). If you wanted to type-parameterise your Node class, instead of having

    You would have

    This generic version is far more reusable, as it is type-parameterised: it can objects of any type, not just Strings.

    Rather than just using a String array of operators, why not use an enum? Here's a partial sample of what it might look like:

    That way, in your RPNCalculator class, you can say:

    Your ReversePolish class (which, again, I'd rename to RPNCalculator for better descriptiveness) is overly simple. Bear in mind that you want to handle ints and operators very differently: With ints you simply want to pop them on to the stack, with operators, you want to pop the next two items off the stack and apply the operator to them. So, how about a couple of methods: public void handleInt(int i) and public void handleOperator(Operator op)?

    I don't want to give you too much help on this, but hopefully I've given you some ideas to move you forward. I think you're still a wee bit away from a decent solution, though, so feel free to ask further questions.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 7973
    143
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I wouldn't make any of the handle methods part of the enum.

    Other than that, great post, have a cow!
     
    Gordon Brown
    Ranch Hand
    Posts: 58
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks! First cow
     
    Campbell Ritchie
    Marshal
    Posts: 56536
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    The only problem is that you are going to have to be careful about the name Stack. There is a built‑in Java® class called Stack which Joshua Bloch says is a triumph of bad design, and there is a risk of confusing the two.
     
    Gordon Brown
    Ranch Hand
    Posts: 58
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    IStack? I've never been a fan of that sort of naming convention though.
     
    Mike. J. Thompson
    Bartender
    Posts: 689
    17
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Oh I hate that naming convention. I would make a terrible C# programmer because I don't think I could bring myself to start all interface names with I.

    In this case I would say that Stack is the best name for the Interface. If an IDE is being used then care needs to be taken if using an auto-import feature to make sure not to import java.utilities.Stack, but it should be fine otherwise.
     
    Gordon Brown
    Ranch Hand
    Posts: 58
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I noticed that I listed the pre/post-conditions etc. for pop(), but suggested that they were those for push(E obj). Apologies for any confusion.
     
    phi tran
    Greenhorn
    Posts: 14
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    thank you for everyone's advice! I redid my program and rename a few things. I still need to work on display() method to show whats on the stack & the RPN part. But this is what I have so far

    //Stack linked list class


    //main
     
    Campbell Ritchie
    Marshal
    Posts: 56536
    172
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Not bad

    Get rid of the no‑arguments Node() constructor. You want to force users always to pass a reference to a value and a next node.
    In the List, don&apost return null. If the list is empty, throw an Exception. You might find java.util.EmptyStackException suitable.
    You should have a peek() method in the stack as well as pop().
    Style: separate all methods by a single empty line.
     
    phi tran
    Greenhorn
    Posts: 14
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    thanks Campbell
     
    phi tran
    Greenhorn
    Posts: 14
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    had some time to work on this again. Had the "Ah Ha!" moment i got so happy. thank you everyone again for tolerating my stupid mistakes.

    Stack linked list - i updated the removeAtHead method, i forgot to have the head Node point to the next Node.


    RPN calculator
     
    Campbell Ritchie
    Marshal
    Posts: 56536
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    You have repeated the Doube.parseDouble calls; I think it appears 8×
    That is a sign that you should be refactoring the code. Code which appears several times should be hived off into a method of its own.

    A different approach is to have a Stack<Double> and do the parsing to doubles before you push anything onto the stack. Since your Stack class is parametrised, I can tell you free how much of it you will have to change. Nothing. But it will require lots of rethinking of the other class.
    Have you ever seen enums? You can make an enum called Operator and add methods to each element of the enum. Those methods can do the arithmetic for you.
     
    Don't get me started about those stupid light bulbs.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!