Question

Using the Stack class (it's on the class web page) construct a program that will evaluate postfix (reverse Polish, more properly reverse Lukasiewicz`notation).

First, create a class called Postfix.  It should have one static function

public static double postfix(String s)
{

This should take a string of tokens consisting of either double constants or the operators + - / *.  It should return the value of the postfix expression as a double.  


The algorithm is
1) Get the next token
2) if it is an operand (double), push it onto a stack.
3) if it is an operator, pop the top two elements, combine them using the operator, and push the result.  For - and /, it matters which popped operand should
be used first.  Entering 2 5 - should give -3.  Entering 5 2 - should give 3.
Similarly 4 2 / should give 2 while 2 4 / gives 0.5

When the last token is processed, the stack should contain 1 element, the anwer.

You need to be prepared to detect and deal with badly formed expressions.
Things to look for are an operator appearing when the stack has 0 or 1 entry
and a situation where there is more than 1 item on the stack after processing the last token.  Be aware of these, and any other problems that may arise, and
shut the program down gracefully with a meaningful error message.

In order to get the tokens 1 by 1 from the input String, you can use
an instance of the StringTokenizer class.  

You should read about this class.  The following code should do the job for you:

import java.util.StringTokenizer;
public class Postfix
{
  public static double postfix(String s)
  {
    StringTokenizer st = new StringTokenizer(s, " +-/*", true);
    //delimiters are space, +, -, /, *.  The "true" says return the 
    //delimiter itself as a token.  

  while (st.hasMoreTokens())
  {
    String tok = st.nextToken();
    // at this point, tok contains " ", "+", "-", "/", "*", or a String
    // representing a double constant.  Anything else is an error.
    // If is a double constant, you can get the double value using
    // Double.parseInt(tok); If this is NOT a double constant, it will
    // throw an exception.  The rest is up to you. 

Here is the stack class

public class Stack<T>
{
  LL<T> theStack;

  public Stack()
  {
    theStack = new LL<T>();
  }

  public boolean isEmpty()
  {
    return this.theStack.isEmpty();
  }

  public boolean isFull()
  {
    return false;
  }

  public void push(T value)
  {
    this.theStack.insertAtHead(value);
  }

  public T pop()
  {
    {
      return this.theStack.removeFromHead();
    }
  }

  public T peek()
  {
    T retval = this.pop();
    this.push(retval);
    return retval;
  }

  public String toString()
  {
    return this.theStack.toString();
  }  

  public static void main(String args[])
  {
    Stack<Double> myStack =  new Stack<Double>();
    
    for (int i = 0; i < 10; i++)
    {
      myStack.push((double)i);
    }

    while (!myStack.isEmpty())
    {
      System.out.println(myStack.pop());
    }
  } 
}

Answer 1

Thanks for the question.


Here is the completed code for this problem. 

Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. 

If you are satisfied with the solution, please rate the answer.

Thanks
===========================================================================

import java.util.Stack;
import java.util.StringTokenizer;

public class Postfix {
    public static double postfix(String s) {
        StringTokenizer st = new StringTokenizer(s, " +-/*", true);
        //delimiters are space, +, -, /, *.  The "true" says return the
        //delimiter itself as a token.
        Stack<Double> numbers = new Stack<Double>();
        while (st.hasMoreTokens()) {
            String tok = st.nextToken().trim();
            // at this point, tok contains " ", "+", "-", "/", "*", or a String
            // representing a double constant.  Anything else is an error.
            // If is a double constant, you can get the double value using
            // Double.parseInt(tok); If this is NOT a double constant, it will
            // throw an exception.  The rest is up to you.

            //3) if it is an operator, pop the top two elements, combine them using the operator, and push the result.  For - and /, it matters which popped operand should
            //be used first.  Entering 2 5 - should give -3.  Entering 5 2 - should give 3.
            if (tok.length() == 0) {
                continue;
            } else if (tok.equals("+") && numbers.size() >= 2) {
                numbers.push(numbers.pop() + numbers.pop());
            } else if (tok.equals("-") && numbers.size() >= 2) {
                double v1=numbers.pop();
                double v2=numbers.pop();
                numbers.push(v2-v1);
            } else if (tok.equals("*") && numbers.size() >= 2) {
                numbers.push(numbers.pop() * numbers.pop());
            } else if (tok.equals("/") && numbers.size() >= 2) {
                double v1=numbers.pop();
                double v2=numbers.pop();
                numbers.push(v2/v1);
            } else {
                //2) if it is an operand (double), push it onto a stack.
                try {
                    double value = Double.parseDouble(tok);
                    numbers.push(value);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                    System.out.println("Invalid number.\nExpression is bad.");
                    return 0.0;
                }
            }
        }
        //When the last token is processed, the stack should contain 1 element, the anwer.
        if (numbers.size() == 1)
            return numbers.pop();
        else
            System.out.println("Invalid number.\nExpression is bad.");
        return 0.0;
    }

    public static void main(String[] args) {

        System.out.println(Postfix.postfix("2 5 -"));
        System.out.println(Postfix.postfix("2 5 - 1 +"));
        System.out.println(Postfix.postfix("2 4 /"));
    }
}

=============================================================================