/*
COSC4301 Stack Example
Class: MyStack
Objectives:
1. Manipulating array of characters
2. 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:
puch: 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.
3. Conversion of Infix-expressions into Postfix-expressions
using two Priorities:
InputPrio StackPrio
+ 1 2
* 3 4
( 10 0
) 0 Undefined
4. Use of simple GUI (Graphical User Interface) for input and output dialog boxes.
Background:
1. 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
2. Any such infix expression has an EQUIVALENT postfix experssion
in which each operator appears right after its two operands.
3. 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 MyStack
{
// 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 MyStack()
{
// The default constructor just calls input()
// in creating a stack object by taking the input
// infix expression
input();
}
public void initialize()
{ push ('(');
}
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);
/* Note that in the above method getChars which converts the calling String, inputt in our case,
into an array of characters, to be named infix, in our example:
1. first argument is the starting index of the string, inputt in this case
2. second argument is the number of characters to form an array of characters
3. third argument is the name of the array of characters being formed
4. last argument represents the starting index, subcript of the array being constructed
*/
if (iSize > MAX)
System.err.println ("ERROR:INPUT EXPRESSION TOO LONG:");
}
///////////////////////////////////////////////////
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 for loop
} // end of convert()
////////////////////////////////////////////////////////////////////////////
public void insertPost (char current)
{
postfix [pSize] = current;
pSize++;
}
////////////////////////////////////////////////////////////////////////////
public boolean isFull()
{
return (top>=MAX);
}
////////////////////////////////////////////////////////////////////////////
public boolean isEmpty()
{
return (top#0);
}
////////////////////////////////////////////////////////////////////////////
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
} // 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 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 pop()
//////////////////////////////////////////////////////////////////////////////
public static void main (String args[])
{
String output = "";
MyStack stack;
for (int times=1; times#=4; times++)
{
stack = new MyStack(); // 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 MyStack