Managing Expressions Using a Stack

Purpose:

The primary focus of module six is stacks, queues, and Priority Queues. Like any other data structure, a stack is a group of objects of the same type. In programming terms, a stack is a data structure in which elements (objects contained within a data structure) are added and removed from only one end. The stack ADT gets its name from the way in which it adds and removes elements. The stack ADT is referred to as a LIFO (Last In, First Out) data structure, meaning that elements are added to the stack's end, one at a time, and must be removed in the reverse order of which they were added. In other words, the stack ADT works like a stack of plates at a salad bar; as each plate is placed on top of the stack, it covers all of the plates beneath it. If someone tried to remove a plate from the middle or bottom of the stack, the result would be an ear-splitting commotion of plates, crashing to the floor. The only way to properly remove plates from the stack is to remove them one at a time from the stack's top -- hence the phrase "Last In, First Out". Whichever plate (element) was added onto the stack last, needs to be removed before any other elements can be removed. For this reason, the stack ADT is designed in such a way that only its end can be manipulated; elements may only be added to or removed from the stack's end. By convention, the end in which elements are added and removed is called the "top" of the stack, the method that adds elements onto the top of the stack is called the "push" method, and the method that removes elements from the top of the stack is called the "pop" method.

The stack ADT is probably the most widely used data structure ever invented. In all of the programming examples that you have completed thus far, including your work in Java I, you have used the stack ADT without even realizing it. Whenever one of your Java applications (or applets) is run on a computer, a certain amount of memory (RAM) is set aside (allocated) to store the necessary variables that your program needs for proper operation. The computer running your application stores these variables on a stack which is generally referred to as the "heap". Each time a method is called within your program, additional RAM must be allocated to store that method's parameters as well as any variables that are created from inside the method itself. All of this data is pushed onto the heap, temporarily, while it is being used. Once the method returns to its caller, the data allocated by the method becomes useless, and the memory consumed by that data is popped off of the heap so that it can be reused by other methods or other applications. Literally, every time you run an application on a computer, you are seeing the stack ADT in action. Since allocation on the heap is dictated by a call-allocate-return-deallocate functionality, the stack ADT is the ideal data structure for managing memory allocation for applications running on a computer.

In this assignment, students will use the java stack provided by the compiler and provides stack functionality to an array-based data structure. Before attempting the assignment, students should carefully read and study Chapter 7 in the textbook.

Goals:

Through the completion of this assignment students should gain hands-on experience with the stack ADT -- its purpose and implementation. Students should learn how the most simple stack -- the array-based stack -- is designed and understand how this type of data structure combines the functionality of the stack ADT with the memory-conservative approach of array-based storage. Students should also incorporate their experience from the previous assignments regarding interfaces to better understand why the stack should be declared as an Abstract Data Type -- that is, a theoretical data structure whose specific inner workings are not as important as its overall functionality; in other words, students should understand that the specific details of how the stack ADT works are not as important as the general details of what it is supposed to do.

Files to be Submitted:

In this assignment students should create one java class called EXP6. The EXP6 class should implement a main method which tests all of the other files created in the assignment. After the assignment has been completed, the file should be submitted for grading into the Dropbox for Assignment 6, which can be found in the Dropbox menu on the course web site. Students should note that only the *.java file for each class/interface needs to be submitted; no *.class files need to be submitted into the Dropbox.

Requirements: EXP6.java

Develop an expression manager that can do a balanced symbol check. Your program will read three different mathematical expressions from the user that are the followings:

a- string expression = "{(0+1)*(2+3)}";

b- string expression = "{(0+1)+[4*(2+3)]}";

c- string expression = "{(0+1)+[4*(2+3)}}";

As you notice the expressions contain the following symbols: { , }, ( , ), [ , ]. Write a program EXP6.java that after it reads the above expressions will check and report whether the expression is balanced or not.Remember that { , }, ( , ), [ , ] are the only symbols that will be checked. All other characters will be ignored.

Remember to use stacks as a mean to process each expression. Call the method that processes the expression as follows:

bool isItBalanced(String inputExpr)

If there is a mismatch in the expression make sure you report the symbol of the mismatch and its actual position in the expression. Return to me the following file by dropping in the Dropbox for Assignment6: EXP6.java.

Run:

Enter your expression: {(0+1)*(2+3)}

Expected output: {(0+1)*(2+3)} == 1

Enter your expression: {(0+1)+[4*(2+3)]}

Expected output: {(0+1)+[4*(2+3)]} == 1

Enter your expression: {(0+1)+[4*(2+3)}}

Mismatch found : } at 15

Expected output: {(0+1)+[4*(2+3)}} == 0