Pseudo code:

 

For each token, t:

If t is a number:

    push (t)

Else 

                 Arg2 = pop();

      Arg1 = pop();

      Result = arg1 +  't' +  arg2; 

      push(result)

End if

End for 

Return pop()

 

 

Convert this pseudo code into java code using this file, complete the push and pop methods using the stack implement in the file. Problem description is provided above:

 

public class LinkedStack {      private class Node {          Node next;          T data;            Node(T e, Node nxt) {              data = e;              next = nxt;          }      }        private Node head = null;        public LinkedStack() { }        /*       * Pushes an item onto the top of this stack.       * Parameters:       *   item - the item to be pushed onto this stack.       * Returns:       *   the item argument.       */      public T push(T item) {          /*           * YOUR CODE HERE           */          return item;      }        /*       * Removes the object at the top of this stack and returns that object as       *   the value of this function.  null is returned if stack is empty       * Returns:       *   The object at the top of this stack or null if stack is empty       */      public T pop() {          /*           * YOUR CODE HERE           */          return null; // This line will change      }        /*       * Tests if this stack is empty.       * Parameters:       *   o - element whose presence in this set is to be tested       * Returns:       *   true if and only if this stack contains no items; false otherwise.       */      public boolean empty() {          return head == null;      }  }

Postfix Expressions Background: Suppose we wanted to evaluate a postfix expression such as 12 +34 + *7/ which in regular infix notation looks like ((1+2) * (3+4))/7 The challenge is that we may have many nested operations. Problem: You need to write an evaluator for these kinds of expressions. Give an algorithm that takes a postfix expression and outputs the result of the expression. Hint: You will need a stack for this! input: LList of numbers, operators and parentheses output: result of expression