CSC 16 Lab 8 (Due next Tuesday) Ever wonder how a compiler checks your program for mismatched ('s and {'s? It's a very nice example of how a STACK data structure can be used. Let's say you have an expression like ((3-4)*(4-1)) - we know the parentheses all match - i.e., that this is a "well formed expression". We can use a stack to verify this as follows: * Start with an empty stack * Every time we see a left parenthesis '(', we push it on to the stack. * Every time we see a right parenthesis ')', we pop a '(' off the stack. * All other characters can simply be skipped. * If at the end of the string the stack becomes empty, that means all parentheses have been matched. On the other hand, if the at the end of the string there are still ('s on the stack, that means we read an expression like ((5+4)-1, i.e., there's a '(' that was not matched by a right parenthesis. Similarly, if we had a string with an unmatched right parenthesis like "(3+4))-1" then when we read the extra ')', there will be no corresponding '(' on the stack to pop. That is, we'll be trying to pop from an empty stack. We can extend this technique to match more than just ()'s but also []'s and {}'s. The algorithm is similar - when we see a left (, [, or { we push it onto the stack. When we see a right ), ], or }, we check the top of the stack, if there's a corresponding (, [, or {, we pop, otherwise, we know that there's a mismatch. For example, with the string "[y=(x+4])", we will detect a mismatch when we look at the ']', because what's on the stack is not a '[' but a '('. Please think this through carefully. IF EVERYTHING WENT PERFECTLY, you should start with an empty stack and end with an empty stack. You know that an error occurred if: 1. You see a ')' (or ] or }) but the stack is empty 2. You see a ') or ']' or '}' but the symbol on top of the stack is not of the right type. For example, a ')' means that the symbol on top of the stack cannot be '[' or '{'. 3. You reach the end of the string, but the stack is not empty. Your program should stop and print an appropriate error message when it detects an error (see sample expected output below). In addition, for an error such as "({[3+4]", which has remaining unmatched left delimiters, your program should be able to automatically "complete" the expression and produced a matched expression, such as "({[3+4]})". That is, when you're at the end of the string and the static is not empty, pop each element off of the stack and add appropriate characters to the end of the string. But be careful. Note that IT IS OK for the stack to become empty before the end of the string has been reached. For example, "(3+x)-(4*y)" is OK, and the stack becomes empty after parsing (3+x). ---------------------------------------------------------------------------- Now for the implementation of the stack, we can use a linked list consisting of the following "symbol cell class" class scell { public final char symbol; public final int position; public final scell tail; public scell(char s, int p, scell t) { symbol=s; position=p; tail=t; } } Note that 1. Instead of just a "head", there are two pieces of information stored in each cell (in addition to the tail link): the character and the position in the string that the character was found (for better error reportage). The use of the position value is optional for your assignment. 2. All the variables are public but "final". This means that the variables are readable from a different class, but once their values are set by the constructor, they cannot be changed. You shouldn't have to change them in this program. To use a linked list of scell objects as a stack, we essentially need a "top of the stack" pointer to the first cell, and implement the operations "push" and "pop". It's preferable to encapsulate these operations inside another class: class sstack // symbolic stack class { private scell tos = null; // top of stack pointer public void push(char s, int p) // add cell in front { tos = new scell(s,p,tos); } // the following function tries to delete the top cell from the stack. // it returns null if the stack is empty, or the cell that was deleted. public scell pop() { if (tos == null) return null; scell oldtos = tos; tos = tos.tail; return oldtos; } // the following function returns the cell at the top of the stack // without popping it public scell peek() { return tos; } public boolean isempty() { return tos==null; } } // sstack For accessing the individual characters of a string, given a String such as String s = "abcd"; s.length() returns the length of the string (4 in this example) s.charAt(i) returns the ith char in the string, 0 being the first char. You can write your program using these classes, or modify them for your needs. The string to be checked can be passed in as a command-line argument, or input in some other way such as with JOptionPane dialogs. The output should be meaningful, such as: # java delimiters "(3+4)+[4-x]" Everything is fine. # java delimiters "((((x))" unmatched ( at char 1, autocompleted as "((((x))))" # java delimiters "(x)]]]" unmatched ] at char 3 # java delimiters "(3+4]+[4-x]" mismatched ( at char 0 and ] at char 4