Question

Assign a new alphabet whenever it sees a new number in those expressions ( Use increment operator(++) so, lets say if x = "a", then x++ would be "b" and so on for as many numbers are there in expressions)

Assignment:Consider the input file “p4in.txt”has the following contents (in java language)
(Assuming that all expressions are correct): so using the valueStack ,uses ArrayStack and operatorStack

Specifications:

1) You must implement ArrayStack.java and modify Positfix.java so that valueStack uses ArrayStack and operatorStack uses LinkedStack.

2) Do this program step by step.

3) It may be easier to use String to split the expression to obtain the array of values.

4) Build your symbol table using single-letter variable name that starts from ‘a’.

Here is the inputfile (p4in.txt)
2 + 3
(2+ 3) * 4
2 * 3 / (4 -5)
2 / 3 + (4 -5)
2 / 3 + c -d
2 ^ 3 ^ 4
(2 ^ 3) ^ 4
2 * (3 / 4 + 5)
(2 + 3) / (4 -5)
2 / (3 -4) * 5
2 - (3 / (4 - 5) * 6 + 0) ^ 1
(2 - 3 * 4) / (5 * 6 ^ 0) * 1 + 8

I need to produce the output file named “p4out.txt” similar to the following:

Here is the output sample p4out.txt
Symbol Table
Variable     Value
a              2
b              3
c              4
d              5
e              6
f              0
g              1
h              8

Input                           Infix    Postfix   Result
2 + 3                           a+b       ab+       5
(2+ 3) * 4                      (a+b)*c   ab+c*    20
2 * 3 / (4 -5)                 all value Omitted downhere
2 / 3 + (4 -5)
2 / 3 + c -d
2 ^ 3 ^ 4
(2 ^ 3) ^ 4
2 * (3 / 4 + 5)
(2 + 3) / (4 -5)
2 / (3 -4) * 5
2 - (3 / (4 - 5) * 6 + 0) ^ 1
(2 - 3 * 4) / (5 * 6 ^ 0) * 1 + 8

Required programs:

ArrayStack.java:

import java.util.Arrays;
import java.util.EmptyStackException;
/**
    A class of stacks whose entries are stored in an array.
    @author Frank M. Carrano
    @author Timothy M. Henry
    @version 4.0
*/
public final class ArrayStack<T> implements StackInterface<T>
{
        private T[] stack;    // Array of stack entries
        private int topIndex; // Index of top entry
   private boolean initialized = false;
        private static final int DEFAULT_CAPACITY = 50;
        private static final int MAX_CAPACITY = 10000;
        
        public ArrayStack()
        {
      this(DEFAULT_CAPACITY);
        } // end default constructor
        
        public ArrayStack(int initialCapacity)
        {
      checkCapacity(initialCapacity);
      
      // The cast is safe because the new array contains null entries
      @SuppressWarnings("unchecked")
      T[] tempStack = (T[])new Object[initialCapacity];
      stack = tempStack;
                topIndex = -1;
      initialized = true;
        } // end constructor

        public void push(T newEntry)
        {
                checkInitialization();
                ensureCapacity();
                stack[topIndex + 1] = newEntry;
                topIndex++;
        } // end push

        public T peek()
        {
                checkInitialization();
                if (isEmpty())
                        throw new EmptyStackException();
                else
         return stack[topIndex];
        } // end peek

        public T pop()
        {
                checkInitialization();
                if (isEmpty())
                        throw new EmptyStackException();
                else
                {
                        T top = stack[topIndex];
                        stack[topIndex] = null;
                        topIndex--; 
         return top;
                } // end if
   } // end pop

   public boolean isEmpty()
        {
                return topIndex < 0;
        } // end isEmpty
        
        public void clear()
        {
                checkInitialization();
      
      // Remove references to the objects in the stack,
      // but do not deallocate the array
                while (topIndex > -1)
      {
                        stack[topIndex] = null;
         topIndex--;
      } // end while
      //        Assertion: topIndex is -1       
        } // end clear
   
   // Throws an exception if this object is not initialized.
   private void checkInitialization()
   {
      if (!initialized)
         throw new SecurityException ("ArrayStack object is not initialized properly.");
   } // end checkInitialization
   
   // Throws an exception if the client requests a capacity that is too large.
   private void checkCapacity(int capacity)
   {
      if (capacity > MAX_CAPACITY)
         throw new IllegalStateException("Attempt to create a stack " +
                                         "whose capacity exceeds " +
                                         "allowed maximum.");
   } // end checkCapacity
    
   // Doubles the size of the array stack if it is full
   // Precondition: checkInitialization has been called.
        private void ensureCapacity()
        {
           if (topIndex >= stack.length - 1) // If array is full, double its size
      {
         int newLength = 2 * stack.length;
         checkCapacity(newLength);
         stack = Arrays.copyOf(stack, newLength);
      } // end if
        } // end ensureCapacity
} // end ArrayStack

LinkedStack.java:

import java.util.EmptyStackException;
/**
   A class of stacks whose entries are stored in a chain of nodes.
   
   @author Frank M. Carrano
   @author Timothy M. Henry
   @version 4.0
*/
public final class LinkedStack<T> implements StackInterface<T>
{
        private Node topNode; // References the first node in the chain
        
        public LinkedStack()
        {
                topNode = null;
        } // end default constructor
        
        public void push(T newEntry)
        {
      topNode = new Node(newEntry, topNode);
//              Node newNode = new Node(newEntry, topNode);
//              topNode = newNode;
        } // end push

        public T peek()
        {
                if (isEmpty())
                        throw new EmptyStackException();
                else
         return topNode.getData();
        } // end peek

        public T pop()
        {
           T top = peek();  // Might throw EmptyStackException
           assert (topNode != null);
      topNode = topNode.getNextNode(); 

           return top;
        } // end pop

/*
// Question 1, Chapter 6: Does not call peek 
        public T pop()
        {
      if (isEmpty())
         throw new EmptyStackException();
      else
                {
         assert (topNode != null);
                        top = topNode.getData();
                        topNode = topNode.getNextNode();
                } // end if
                
                return top;
        } // end pop
*/              

        public boolean isEmpty()
        {
                return topNode == null;
        } // end isEmpty
        
        public void clear()
        {
                topNode = null;  // Causes deallocation of nodes in the chain
        } // end clear

        private class Node
        {
      private T    data; // Entry in stack
      private Node next; // Link to next node

      private Node(T dataPortion)
      {
         this(dataPortion, null);
      } // end constructor

      private Node(T dataPortion, Node linkPortion)
      {
         data = dataPortion;
         next = linkPortion;    
      } // end constructor

      private T getData()
      {
         return data;
      } // end getData

      private void setData(T newData)
      {
         data = newData;
      } // end setData

      private Node getNextNode()
      {
         return next;
      } // end getNextNode

      private void setNextNode(Node nextNode)
      {
         next = nextNode;
      } // end setNextNode
        } // end Node
} // end LinkedStack

Postfix.java:

/**
   A class that represents a postfix expression.
   Based on pseudocode in Segments 5.16 and 5.18.

   @author Frank M. Carrano
   @author Timothy M. Henry
   @version 4.0
*/
public class Postfix
{
   /** Creates a postfix expression that represents a given infix expression.
       Segment 5.16.
       @param infix  A string that is a valid infix expression.
       @return  A string that is the postfix expression equivalent to infix. */
   public static String convertToPostfix(String infix)
   {
      StackInterface<Character> operatorStack = new LinkedStack<Character>();
      StringBuilder postfix = new StringBuilder();
      int characterCount = infix.length();
      char topOperator;

      for (int index = 0; index < characterCount; index++)
      {
         boolean done = false;
         char nextCharacter = infix.charAt(index);

         if (isVariable(nextCharacter))
            postfix = postfix.append(nextCharacter);
         else
         {
            switch (nextCharacter)
            {
               case '^':
                  operatorStack.push(nextCharacter);
                  break;

               case '+': case '-': case '*': case '/':
                  while (!done && !operatorStack.isEmpty())
                  {
                     topOperator = operatorStack.peek();

                     if (getPrecedence(nextCharacter) <= getPrecedence(topOperator))
                     {
                        postfix = postfix.append(topOperator);
                        operatorStack.pop();
                     }
                     else
                        done = true;
                  } // end while

                  operatorStack.push(nextCharacter);
                  break;

               case '(':
                  operatorStack.push(nextCharacter);
               break;

               case ')': // Stack is not empty if infix expression is valid
                  topOperator = operatorStack.pop();
                  while (topOperator != '(')
                  {
                     postfix = postfix.append(topOperator);
                     topOperator = operatorStack.pop();
                  } // end while
                  break;

               default: break; // Ignore unexpected characters
            } // end switch
         } // end if
      } // end for

      while (!operatorStack.isEmpty())
      {
         topOperator = operatorStack.pop();
         postfix = postfix.append(topOperator);
      } // end while

      return postfix.toString();
   } // end convertToPostfix

   // Indicates the precedence of a given operator.
   // Precondition: operator is a character that is (, ), +, -, *, /, or ^.
   // Returns an integer that indicates the precedence of operator:
   //         0 if ( or ), 1 if + or -, 2 if * or /, 3 if ^,
   //         -1 if anything else. */
   private static int getPrecedence(char operator)
   {
      switch (operator)
      {
         case '(': case ')': return 0;
         case '+': case '-': return 1;
         case '*': case '/': return 2;
         case '^':           return 3;
      } // end switch

      return -1;
   } // end getPrecedence

   private static boolean isVariable(char character)
   {
      return Character.isLetter(character);
   } // end isVariable

   /** Evaluates a postfix expression.
       Segment 5.18
       @param postfix  a string that is a valid postfix expression.
       @return  the value of the postfix expression. */
   public static double evaluatePostfix(String postfix)
   {
      StackInterface<Double> valueStack = new LinkedStack<Double>();
      int characterCount = postfix.length();

      for (int index = 0; index < characterCount; index++)
      {
         char nextCharacter = postfix.charAt(index);

         switch(nextCharacter)
         {
            case 'a': case 'b': case 'c': case 'd': case 'e':
               valueStack.push(valueOf(nextCharacter));
               break;

            case '+': case '-': case '*': case '/': case '^':
               Double operandTwo = valueStack.pop();
               Double operandOne = valueStack.pop();
               Double result = compute(operandOne, operandTwo, nextCharacter);
               valueStack.push(result);
               break;

            default: break; // Ignore unexpected characters
         } // end switch
      } // end for

      return (valueStack.peek()).doubleValue();
   } // end evaluatePostfix

   private static double valueOf(char variable)
   {
      switch (variable)
      {
         case 'a': return 2.5;
         case 'b': return 3.0;
         case 'c': return 4.0;
         case 'd': return 12.0;
         case 'e': return 16.5;
      } // end switch

      return 0; // Unexpected character
   } // end valueOf

   private static Double compute(Double operandOne, Double operandTwo, char operator)
   {
      double result;

      switch (operator)
      {
         case '+':
            result = operandOne.doubleValue() + operandTwo.doubleValue();
            break;

         case '-':
            result = operandOne.doubleValue() - operandTwo.doubleValue();
            break;

         case '*':
            result = operandOne.doubleValue() * operandTwo.doubleValue();
             break;

         case '/':
            result = operandOne.doubleValue() / operandTwo.doubleValue();
            break;

         case '^':
            result = Math.pow(operandOne.doubleValue(), operandTwo.doubleValue());
            break;

         default:    // Unexpected character
            result = 0;
            break;
      } // end switch

      return result;
   } // end compute
} // end Postfix

StackInterface.java:

/**
   An interface for the ADT stack.
   @author Frank M. Carrano
   @author Timothy M. Henry
   @version 4.0
*/
public interface StackInterface<T>
{
   /** Adds a new entry to the top of this stack.
       @param newEntry  An object to be added to the stack. */
   public void push(T newEntry);
  
   /** Removes and returns this stack's top entry.
       @return  The object at the top of the stack. 
       @throws  EmptyStackException if the stack is empty before the operation. */
   public T pop();
  
   /** Retrieves this stack's top entry.
       @return  The object at the top of the stack.
       @throws  EmptyStackException if the stack is empty. */
   public T peek();
  
   /** Detects whether this stack is empty.
       @return  True if the stack is empty. */
   public boolean isEmpty();
  
   /** Removes all entries from this stack. */
   public void clear();
} // end StackInterface

Driver.java:

/**
   A driver that demonstrates the class Postfix.
   
   @author Frank M. Carrano
   @author Timothy M. Henry
   @version 4.1
*/
public class Driver
{
        public static void main(String[] args) 
        {
                System.out.println("Testing postfix expressions with\n" +
                                   "a = 2, b = 3, c = 4, d = 5, e = 6\n\n");

                testPostfix("a+b");
                testPostfix("(a + b) * c");
                testPostfix("a * b / (c - d)");
                testPostfix("a / b + (c - d)");
                testPostfix("a / b + c - d");
                testPostfix("a^b^c");
                testPostfix("(a^b)^c");
                testPostfix("a*(b/c+d)");

                System.out.println("Testing Question 6, Chapter 5:\n");
                testPostfix("(a+b)/(c-d)");         // Question 6a, Chapter 5
                testPostfix("a/(b-c)*d");           // Question 6b
                testPostfix("a-(b/(c-d)*e+f)^g");   // Question 6c
                testPostfix("(a-b*c)/(d*e^f*g+h)"); // Question 6d

                System.out.println("Testing Question 7, Chapter 5:\n");
                System.out.println("Q7a: ae+bd-/ : "   + Postfix.evaluatePostfix("ae+bd-/") + "\n");
                System.out.println("Q7b: abc*d*- : "   + Postfix.evaluatePostfix("abc*d*-") + "\n");
                System.out.println("Q7c: abc-/d* : "   + Postfix.evaluatePostfix("abc-/d*") + "\n");
                System.out.println("Q7d: ebca^*+d- : " + Postfix.evaluatePostfix("ebca^*+d-") + "\n");
                System.out.println("\n\nDone.");
        }  // end main
        
        public static void testPostfix(String infixExpression)
        {
                System.out.println("Infix:   " + infixExpression);
                String postfixExpression =  Postfix.convertToPostfix(infixExpression);
                System.out.println("Postfix: " + postfixExpression);
                System.out.println("\n");
        } // end testPostfix 
}  // end Driver

/*
 Testing postfix expressions with
 a = 2, b = 3, c = 4, d = 5, e = 6
 
 
 Infix:   a+b
 Postfix: ab+
 
 
 Infix:   (a + b) * c
 Postfix: ab+c*
 
 
 Infix:   a * b / (c - d)
 Postfix: ab*cd-/
 
 
 Infix:   a / b + (c - d)
 Postfix: ab/cd-+
 
 
 Infix:   a / b + c - d
 Postfix: ab/c+d-
 
 
 Infix:   a^b^c
 Postfix: abc^^
 
 
 Infix:   (a^b)^c
 Postfix: ab^c^
 
 
 Infix:   a*(b/c+d)
 Postfix: abc/d+*
 
 
 Testing Question 6, Chapter 5:
 
 Infix:   (a+b)/(c-d)
 Postfix: ab+cd-/
 
 
 Infix:   a/(b-c)*d
 Postfix: abc-/d*
 
 
 Infix:   a-(b/(c-d)*e+f)^g
 Postfix: abcd-/e*f+g^-
 
 
 Infix:   (a-b*c)/(d*e^f*g+h)
 Postfix: abc*-def^*g*h+/
 
 
 Testing Question 7, Chapter 5:
 
 Q7a: ae+bd-/ : -4.0
 
 Q7b: abc*d*- : -58.0
 
 Q7c: abc-/d* : -10.0
 
 Q7d: ebca^*+d- : 49.0
 
 
 
 Done.
 */

Answer 1

Driver.java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Driver
{
   public static void main(String[] args) throws FileNotFoundException {

       File text = new File("p4in.txt");
       CreateFile aFile = new CreateFile();
       aFile.openFile("p4out.txt");
       Scanner scnr = new Scanner(text);

       String s = String.format("%-40s%-30s%-30s%s", "Input", "Infix", "Postfix", "Result\n");
       String s2 = String.format("%65s%59s%8s%59s%8s", "Symbol Table\n", "Variable", "Value\n", "--------", "--------\n");
       String s3 = String.format("%56s%9s%56s%9s%56s%9s%56s%9s%56s%9s%56s%9s%56s%9s%56s%9s"
               , "a", "2\n", "b", "3\n", "c", "4\n", "d", "5\n", "e", "6\n", "f", "0\n", "g", "1\n", "h", "8\n");
       System.out.println(s2 + "\n" + s3);
       aFile.addRecords(s2);
       aFile.addRecords(s3);
       aFile.addRecords(s);
       System.out.println(s);
       while (scnr.hasNextLine()) {
           String line = scnr.nextLine();
           testPostfix(line, aFile);

       }

       aFile.closeFile();
   }
  
   public static void testPostfix(String input, CreateFile aFile)
   {

       String infixExpression = Postfix.convertToInfix(input);

       String postfixExpression = Postfix.convertToPostfix(infixExpression);

       double result = Postfix.evaluatePostfix(postfixExpression);

       String record = String.format("%-40s%-30s%-30s%s\n",input,infixExpression,postfixExpression,result);
       aFile.addRecords(record);
       System.out.println(record);
       System.out.println("\n");
   } // end testPostfix

} // end Driver

Postfix.java

public class Postfix
{

   public static String convertToInfix(String infix) {
      StackInterface<Character> operatorStack = new LinkedStack<Character>();
      StringBuilder infixExpression = new StringBuilder();
      int characterCount = infix.length();
      char topOperator;

      for (int index = 0; index < characterCount; index++) {
         char nextCharacter = infix.charAt(index);

         if (isInteger(nextCharacter)) {

            nextCharacter = characterChange(nextCharacter);
            infixExpression.append(nextCharacter);
         }
         else {
            switch (nextCharacter)
            {
               case 'a': case 'b': case 'c': case 'd': case 'e':case 'f': case 'g':case 'h':
               infixExpression.append(nextCharacter);
               break;               case '^':
               infixExpression.append(nextCharacter);
               break;

               case '+': case '-': case '*': case '/':
               infixExpression.append(nextCharacter);

               break;

               case '(':
                  infixExpression.append(nextCharacter);
                  break;

               case ')': // Stack is not empty if infix expression is valid

                  infixExpression.append(nextCharacter);
                  break;

               default: break; // Ignore unexpected characters
            } // end switch
         } // end if
      } // end for

      while (!operatorStack.isEmpty())
      {
         topOperator = operatorStack.pop();
         infixExpression = infixExpression.append(topOperator);
      } // end while

      return infixExpression.toString();
   } // end convertToPostfix

   /** Creates a postfix expression that represents a given infix expression.
       Segment 5.16.
       @param infix A string that is a valid infix expression.
       @return A string that is the postfix expression equivalent to infix. */
   public static String convertToPostfix(String infix)
   {
      StackInterface<Character> operatorStack = new LinkedStack<Character>();
      StringBuilder postfix = new StringBuilder();
      int characterCount = infix.length();
      char topOperator;

      for (int index = 0; index < characterCount; index++)
      {
         boolean done = false;
         char nextCharacter = infix.charAt(index);

         if (isVariable(nextCharacter))
            postfix = postfix.append(nextCharacter);
         else
         {
            switch (nextCharacter)
            {
               case '^':
                  operatorStack.push(nextCharacter);
                  break;

               case '+': case '-': case '*': case '/':
                  while (!done && !operatorStack.isEmpty())
                  {
                     topOperator = operatorStack.peek();

                     if (getPrecedence(nextCharacter) <= getPrecedence(topOperator))
                     {
                        postfix = postfix.append(topOperator);
                        operatorStack.pop();
                     }
                     else
                        done = true;
                  } // end while

                  operatorStack.push(nextCharacter);
                  break;

               case '(':
                  operatorStack.push(nextCharacter);
               break;

               case ')': // Stack is not empty if infix expression is valid
                  topOperator = operatorStack.pop();
                  while (topOperator != '(')
                  {
                     postfix = postfix.append(topOperator);
                     topOperator = operatorStack.pop();
                  } // end while
                  break;

               default: break; // Ignore unexpected characters
            } // end switch
         } // end if
      } // end for

      while (!operatorStack.isEmpty())
      {
         topOperator = operatorStack.pop();
         postfix = postfix.append(topOperator);
      } // end while

      return postfix.toString();
   } // end convertToPostfix

   private static int getPrecedence(char operator)
   {
      switch (operator)
      {
         case '(': case ')': return 0;
         case '+': case '-': return 1;
         case '*': case '/': return 2;
         case '^':           return 3;
      } // end switch

      return -1;
   } // end getPrecedence

   private static boolean isVariable(char character)
   {
      return Character.isLetter(character);
   } // end isVariable
   private static boolean isInteger(char character){return Character.isDigit(character);}

   /** Evaluates a postfix expression.
       Segment 5.18
       @param postfix a string that is a valid postfix expression.
       @return the value of the postfix expression. */
   public static double evaluatePostfix(String postfix)
   {
      StackInterface<Double> valueStack = new ArrayStack<Double>();
      int characterCount = postfix.length();

      for (int index = 0; index < characterCount; index++)
      {
         char nextCharacter = postfix.charAt(index);

         switch(nextCharacter)
         {
            case 'a': case 'b': case 'c': case 'd': case 'e':case 'f': case 'g':case 'h':
               valueStack.push(valueOf(nextCharacter));
               break;

            case '+': case '-': case '*': case '/': case '^':
               Double operandTwo = valueStack.pop();
               Double operandOne = valueStack.pop();
               Double result = compute(operandOne, operandTwo, nextCharacter);
               valueStack.push(result);
               break;

            default: break; // Ignore unexpected characters
         } // end switch
      } // end for

      return (valueStack.peek());
   } // end evaluatePostfix

   private static double valueOf(char variable)
   {
      switch (variable)
      {
         case 'a': return 2;
         case 'b': return 3;
         case 'c': return 4;
         case 'd': return 5;
         case 'e': return 6;
         case 'f': return 0;
         case 'g': return 1;
         case 'h': return 8;
      } // end switch

      return 0; // Unexpected character
   } // end valueOf

   private static Double compute(Double operandOne, Double operandTwo, char operator)
   {
      double result;

      switch (operator)
      {
         case '+':
            result = operandOne + operandTwo;
            break;

         case '-':
            result = operandOne - operandTwo;
            break;

         case '*':
            result = operandOne * operandTwo;
             break;

         case '/':
            result = operandOne / operandTwo;
            break;

         case '^':
            result = Math.pow(operandOne, operandTwo);
            break;

         default:    // Unexpected character
            result = 0;
            break;
      } // end switch

      return result;
   } // end compute

   public static char characterChange(char nextCharacter){

      switch(nextCharacter)
      {
         case '2': nextCharacter='a';
            break;
         case '3': nextCharacter='b';
            break;
         case '4': nextCharacter='c';
            break;
         case '5': nextCharacter='d';
            break;
         case '6': nextCharacter='e';
            break;
         case '0': nextCharacter='f';
            break;
         case '1': nextCharacter='g';
            break;
         case '8': nextCharacter='h';
         default:break;
      }
      return nextCharacter;
   }
} // end Postfix

CreateFile.java

import java.util.Formatter;

public class CreateFile {

    private Formatter file;

    //creates a file accepting a string representation of the path
    public void openFile(String filePath){
        try {
            file = new Formatter(filePath);
        }
        catch (Exception e){
            System.out.println("An error has occurred.");
        }
    }

    public void addRecords(String record){
        file.format("%S", record);
    }

    public void closeFile(){
        file.close();
    }
}

StackInterface.java

public interface StackInterface<T>
{
   /** Adds a new entry to the top of this stack.
       @param newEntry An object to be added to the stack. */
   public void push(T newEntry);

   /** Removes and returns this stack's top entry.
       @return The object at the top of the stack.
       @throws EmptyStackException if the stack is empty before the operation. */
   public T pop();

   /** Retrieves this stack's top entry.
       @return The object at the top of the stack.
       @throws EmptyStackException if the stack is empty. */
   public T peek();

   /** Detects whether this stack is empty.
       @return True if the stack is empty. */
   public boolean isEmpty();

   /** Removes all entries from this stack. */
   public void clear();
} // end StackInterface

ArrayStack.java

import java.util.Arrays;
import java.util.EmptyStackException;

public final class ArrayStack<T> implements StackInterface<T> {

    private T[] stack;
    private int topIndex;
    private boolean initialized = false;
    private static final int DEFAULT_CAPACITY = 50;
    private static final int MAX_CAPACITY = 10000;

    public ArrayStack() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayStack(int initialCapacity) {

        checkCapacity(initialCapacity);

        @SuppressWarnings("unchecked")
                T[] tempStack = (T[])new Object[initialCapacity];
        stack = tempStack;
        topIndex = -1;
        initialized = true;
    }
    /** Adds a new entry to the top of this stack.
     @param newEntry An object to be added to the stack. */
    public void push(T newEntry) {
        checkInitialization();
        ensureCapacity();
        stack[topIndex + 1] = newEntry;
        topIndex++;
    }

    /** Removes and returns this stack's top entry.
     @return The object at the top of the stack.
     @throws EmptyStackException if the stack is empty before the operation. */
    public T pop() {
        checkInitialization();
        if(isEmpty()){
            throw new EmptyStackException();
        }
        else {
            T top = stack[topIndex];
            stack[topIndex] = null;
            topIndex--;
            return top;
        }

    }

    /** Retrieves this stack's top entry.
     @return The object at the top of the stack.
     @throws EmptyStackException if the stack is empty. */
    public T peek() {
        checkInitialization();
        if(isEmpty())
            throw new EmptyStackException();
        else
            return stack[topIndex];
    }

    /** Detects whether this stack is empty.
     @return True if the stack is empty. */
    public boolean isEmpty() {

        return topIndex < 0;
    }

    /** Removes all entries from this stack. */
    public void clear() {

        while(!isEmpty()){
            pop();
        }

    }

    private void checkInitialization(){
        if (!initialized)
            throw new SecurityException("Array object is not initialized properly.");
    }

    private void checkCapacity(int capacity){
        if (capacity > MAX_CAPACITY)
            throw new IllegalStateException("Attempt to create a bag whose capacity exceeds allowed maximum"
            + "of " + MAX_CAPACITY);
    }

    private void ensureCapacity(){
         if (topIndex == stack.length - 1){
             int newLength = 2 * stack.length;
             checkCapacity(newLength);
             stack = Arrays.copyOf(stack, newLength);
         }
    }
} // end StackInterface

LinkedStack.java

import java.util.EmptyStackException;

public final class LinkedStack<T> implements StackInterface<T>
{
   private Node topNode; // References the first node in the chain
  
   public LinkedStack()
   {
       topNode = null;
   } // end default constructor
  
   public void push(T newEntry)
   {
      topNode = new Node(newEntry, topNode);
//       Node newNode = new Node(newEntry, topNode);
//       topNode = newNode;
   } // end push

   public T peek()
   {
       if (isEmpty())
           throw new EmptyStackException();
       else
         return topNode.getData();
   } // end peek

   public T pop()
   {
       T top = peek(); // Might throw EmptyStackException
       assert (topNode != null);
      topNode = topNode.getNextNode();

       return top;
   } // end pop

   public boolean isEmpty()
   {
       return topNode == null;
   } // end isEmpty
  
   public void clear()
   {
       topNode = null; // Causes deallocation of nodes in the chain
   } // end clear

   private class Node
   {
      private T    data; // Entry in stack
      private Node next; // Link to next node

      private Node(T dataPortion)
      {
         this(dataPortion, null);
      } // end constructor

      private Node(T dataPortion, Node linkPortion)
      {
         data = dataPortion;
         next = linkPortion;  
      } // end constructor

      private T getData()
      {
         return data;
      } // end getData

      private void setData(T newData)
      {
         data = newData;
      } // end setData

      private Node getNextNode()
      {
         return next;
      } // end getNextNode

      private void setNextNode(Node nextNode)
      {
         next = nextNode;
      } // end setNextNode
   } // end Node
} // end LinkedStack

p4in.txt

2 + 3
( 2 + 3) * 4
2 * 3 / (4 - 5)
2 / 3 + (4 - 5)
2 / 3 + c - d
2 ^ 3 ^ 4
(2 ^ 3) ^ 4
2 * (3 / 4 + 5)
(2 + 3) / (4 - 5)
2 / (3 - 4) * 5
2 - (3 / (4 - 5) * 6 + 0) ^ 1
(2 - 3 * 4) / (5 * 6 ^ 0) * 1 + 8