Write a method named fullyParens() that uses stacks to evaluate fully parenthesized expressions with variables. You should use 3 stacks: one for the operators, one for the parenthesis (or brackets or braces), and one for the operands. For this exercise, every time you see the word “parenthesis”, keep in mind that it may well be a bracket (“[“) or a brace (“{“).

There will only be two types of expressions:

• variableName=integerConstant
• variableName:expression

 

Implementation details:

• Every time you see an operand, push it into the operand stack.
• Every time you see an operator, push it into the operator stack.
• Every time you see an opening parenthesis, push it into the parenthesis stack.
• Every time you see a closing parenthesis, then it is time to evaluate a sub-expression! First, make sure the closing parenthesis matches the opening one. Then, to evaluate the subexpression inside the parenthesis, you will need to pop the operand stack twice to obtain the two operands, and pop the operator stack once to know what operation will be performed with those two operands. If the parenthesis doesn’t match, or if the operator stack is empty, or if the operand stack does not have at least two elements, then the expression is invalid and you should indicate so immediately by printing a message to the screen (see sample output below).
• Your program should continually prompt for input and finish when no new input is entered (until input entered is ""). In the end, print the final values for the variables like in the example shown

 

You may assume that:

• Variable names will consist of a capital letter, so you’ll have at most 26 variables.
• We will be using only integer values.
• There will be no spaces in the expressions.

 

Hint 1: You may use an array of type Integer to store the variable values, where variable A is at index 0, variable B is at index 1, etc. Unlike int, Integer allows you to use null to initialize the array entries, so that you may easily keep track of which variables actually exist.

Hint 2: Variables may be considered as characters or strings of length 1. However, when you evaluate a sub-expression, it will result in an integer value, which will have to be pushed into the operand stack. The problem is you can’t push an Integer into a Character/String stack or vice-versa. Hence, you should declare your operand stack to be of type Integer, and when you encounter a variable, push its value (Integer) onto the stack instead of the variable name (Character/String).

Think: What type of changes would you need to implement so that an expression like A+X would be considered valid (i.e. so that the expression doesn’t have to be fully parenthesized)?

YOU MUST USE THREE STACKS, IMPLEMENTATIONS THAT DO NOT USE STACKS OR THAT ARE FORCED OUTPUTS WILL RECEIVE ZERO CREDIT

Example:

import java.util.EmptyStackException; import java.util.Scanner; public class Lab06ParensWrapper {     public static interface Stack {         public int size();        public boolean isEmpty();        public void clear();        public void push(E e);        public E pop();        public E top(); //A.K.A. peek()     }     public static class LinkedStack implements Stack{         @SuppressWarnings("hiding")        private class Node {             private E element;            private Node next;             public Node(E elm, Node next) {                this.element = elm;                this.next = next;            }             public Node(E elm) {                this(elm, null);            }             public Node() {                this(null, null);            }             public void clear() {                this.element = null;                this.next = null;            }             public E getElement() {                return element;            }             public void setElement(E element) {                this.element = element;            }             public Node getNext() {                return next;            }             public void setNext(Node next) {                this.next = next;            }        }         private int currentSize;        private Node header;         public LinkedStack() {            this.currentSize =0;            this.header = new Node<>();        }         @Override        public int size() {            return currentSize;        }         @Override        public boolean isEmpty() {            return size() == 0;        }         @Override        public void clear() {            while(!isEmpty()) pop();        }         /**         * Note: For operations to be O(1),          * header will always point to the top of the stack         *         * Example:         * header -> Jim -> Bob -> Ned -> Jil -> Kim -> null         *         * Example:         * newNode = Jim         * header -> Jim -> null         *         * Bob <- Top of stack         * Ned         * Jil         * Kim          */        @Override        public void push(E e) {            //Equivalent to SLL.add(e, 0)            Node newNode;            if(isEmpty())                newNode = new Node<>(e);            else                newNode = new Node<>(e, header.getNext());             header.setNext(newNode);            currentSize++;        }         @Override        public E pop() {            //Equivalent to SLL.remove(0)            if(isEmpty())                throw new EmptyStackException();             Node curNode = header;            Node rmNode = curNode.getNext();            E value = rmNode.getElement();             curNode.setNext(rmNode.getNext());            rmNode.clear();            rmNode = null;            currentSize--;             return value;        }         @Override        public E top() {            //Equivalent to SLL.get(0)            if(isEmpty())                throw new EmptyStackException();            return header.getNext().getElement();        }     }     /**     * You can implement any auxiliary function, as well as declare any static      * fields inside this wrapper class to help you out.     * For ease of use declare the static fields here, above this method     */    public static void fullyParens() {        /**************************         * TODO ADD YOUR CODE HERE*         **************************/    }     /**********************************     * ADD YOUR AUXILIARY METHODS HERE*     **********************************/ } 

Input Lab06ParensWrapper.fullyParens (); L=5 W=10 A: (L*W) X=100 L: [X-W] L: (A-X)) L: ((A-X) J: ([X-(A/W])*L) J: ([X-(A/W)]*L) W=10 W:A+X X=100 L: ((L+A) *W) Test Result L: (A-X)) is invalid L: ((A-X) is invalid J:([X-(A/W]) *L) is invalid W:A+X is invalid A=50 J=8550 L=1400