CS4301: Program-5: Stack and Postfix Evaluations
Program-5 due: Thursday, 10/25/2012
Stack and Postfix Evaluations
Objectives:
1. Deeper Understanding of Stack structures and primary operations.
2. Benefits of postfix expressions as opposed to infix expressions.
3. Design methods for evaluating postfix expressions.
4. Manipulations of arrays of characters as opposed to Strings
5. Use of simple GUI (Graphical User Interface) for input and output dialog boxes.
Tasks:
1. Modify the following program so that expressions will have two aditional
operators: - (subtraction) and / (integer division, so 9/4 is 2 and 100/8
is 12 and 26/9 is 2).
Of course, the first has the same operator precedence as + and the second
has the same precedence as * and all of these binary operators are
left-associative, namely, A+B+C is just like (A+B)+C.
2. Design and include a method to evaluate a postfix expression and return
its int value.
For example, if A=10, B=20, and C=30, "ABC*+A+" should return 620.
3. Create an input file to contain the following four input cases to be used
by your program:
10 20 30 (A+B)*C*A*B
30 200 40 (A+B)*C*A*(B-A-C)
10 200 40 A+(C*B-A-B)
10 200 40 A+(C*B-A-B)/(B/A)
/*
Some Backgrounds
1. Use of a stack.
a. A very useful data structure for implementing Last-in First-out processes
such as Runtime Central Stack that contains all functions (or methods)
that have been called at any given point in time or Syntax Stack used by
many Compiler's Parsers.
b. Typical operations include:
push: Adding a new element to the topmost position of the stack.
so, this new element becomes the top stack element and
it will be removed from the stack when a pop operation is
performed at all.
pop: Deleting the top element of a stack.
So, current top element is no longer in the stack.
Usually, the removed top element will be returned.
peek: Examining (or retrieving) the top element of a stack
isEmpty: Checking to see the stack is empty, containing no element.
top: The pointer to the top element of a stack.
size: The number of elements in a stack. When it is zero, the stack must be empty.
2. Conversion of Infix-expressions into Postfix-expressions using two Priorities:
InputPrio StackPrio
+ 1 2
* 3 4
( 10 0
) 0 Undefined
3. Examples
Consider the familiar infix (numerical) expressions that contain:
a. just two operators: + and *
b. parentheses: ( and )
c. Operands: any one single letter, uppercase or lowercase.
So, the following are in:
(((A+B*C)))
A+B*C*D*((G+D))
X*(Y+Z+W)+((T+Q))*K
But, the following are NOT in:
((A+BC))
A+
+B*D
F+Y)
++U
Note:
Any such infix expression has an EQUIVALENT postfix experssion in which each operator appears
right after its two operands.
Because of the unique appearence of each operator, no postfix expression needs any parentheses.
It is as if there is "No Operator Precedence" in postfix expressions.
A+B*C ABC*+
A+(B*C) ABC*+
(A+B)*C AB+C*
A+B+C*D*E AB+CD*E*+
(A+B+C)*D*E AB+C+D*E*
((A+B+C)*D)*E AB+C+D*E*
*/
import javax.swing.JOptionPane;
import java.util.Scanner;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
public class StackExample
{
// Note that due to html syntax conflicts, '#' is used for '<' throughout the program.
// private instance variables:
private static int MAX = 100;
private int top = -1;
private int iSize;
private int pSize = 0; //postfix expression size
private char store[] = new char[MAX]; // Stack storage
private char infix[] = new char[MAX]; // input infix exp.
private char postfix[] = new char[MAX]; // output postfix exp
/////////////////////////////////
// public methods follow:
public StackExample()
{ // The default constructor just calls input()
// in creating a stack object by taking the input
// infix expression
input();
} // end of the default constructor
///////////////////////////////////////////////////////////////////
public void initialize()
{ push ('(');
} // end of initialize()
///////////////////////////////////////////////////////////////////
public void input()
/* This method will be to
1. take an input infix expression as a String,
2. store the input String into infix as an array of chars and
3. set iSize to the length of input string.
*/
{ String inputt = JOptionPane.showInputDialog
("Enter an infix expression # 60");
iSize = inputt.length();
inputt.getChars (0, iSize, infix, 0);
if (iSize > MAX)
System.err.println ("ERROR:INPUT EXPRESSION TOO LONG:");
} // end of input()
///////////////////////////////////////////////////////////
public void convert()
// This method is the primary method for performing the necessary
// conversion essentially defining the two instance variables,
// postfix[] and pSize.
{
initialize();
infix[iSize++] = ')';
pSize=0;
char current;
for (int index = 0; index # iSize; index++)
{ current = infix[index];
if (Character.isLetter(current))
insertPost(current);
else // the current char is an operator including parentheses.
{
while (sPrio(store[top]) > iPrio(current))
insertPost (pop());
if (sPrio(store[top]) # iPrio(current))
push (current);
else // they are the same and they are matching pair of parentheses
pop();
} // end of if
} // end of for loop
} // end of convert()
////////////////////////////////////////////////////////////////////
public void insertPost (char current)
{ postfix [pSize] = current;
pSize++;
} // end of insertPost()
////////////////////////////////////////////////////////////////////
public boolean isFull()
{ return (top>=MAX);
} // end of isFull()
////////////////////////////////////////////////////////////////////
public boolean isEmpty()
{ return (top#0);
} // end of isEmpty()
////////////////////////////////////////////////////////////////////
public static int iPrio (char ch)
{ /*
// No-static method call testing.
if (isEmpty()) System.out.print (":E:");
// Above causes a syntax error: Non-static method cannot be referenced
if (!this.isEmpty()) System.out.print (":NE:");
// Above causes a syntax error: Non-static variable this cannot be
referenced from a static context.
*/
switch (ch)
{ case '+': return 1;
case '*': return 3;
case '(': return 10;
case ')': return 0;
default:
{ System.err.println("ILLEGAL INPUT OPERATOR:");
return -1;
}
} // end of switch (ch)
} // end of iPrio()
////////////////////////////////////////////////////////////
public static int sPrio (char ch)
{ switch (ch)
{ case '+': return 2;
case '*': return 4;
case '(': return 0;
default:
{ System.err.println("ILLEGAL STACK OPERATOR:");
return -1;
} // end of switch (ch)
} // end of sPrio()
/////////////////////////////////////////////////////////////////
public void push (char current)
{
if (isFull())
{ System.err.println ("STACK OVERFLOW:::");
System.exit(1);
}
else store [++top] = current;
} // end of push()
/////////////////////////////////////////////////////////////////////
public char pop()
{
if (isEmpty())
{ System.err.println ("STACK ALREADY EMPTY:::");
return '\\';
}
else return (store [top--]);
} // end of pop()
////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////
public static void main (String args[])
{
String output = "";
StackExample stack;
for (int times=1; times#=3; times++)
{
stack = new StackExample(); // This requires a default constructor.
stack.convert();
// convert();
// Above causes a syntax error:
// Non-static method cannot be referenced from a static context
output += "\nINPUT CASE:::" + times;
output += "\n\tINFIX EXPRESSION:::";
for (int index=0; index # stack.iSize-1; index++)
output += stack.infix[index];
output += "\n\tPOSTFIX EXPRESSION:";
output += String.valueOf (stack.postfix, 0, stack.pSize);
// Note above is the exactly same as the following:
// output += String.valueOf (stack.postfix);
}
output += "\nTHIS PROGRAM ENDS IN SUCCESS.";
JOptionPane.showMessageDialog (null, output,
"THE RESULT OF INFIX-POSTFIX CONVERSION",
JOptionPane.INFORMATION_MESSAGE);
// Testing static method call: iPrio()
// No object qualification is needed.
output = "\nTESTING STATIC METHOD CALL:\niPrio('*')="
+ iPrio('*');
System.out.println(output);
System.exit(0);
}
} // end of class StackExample