java program to evaluate math expressions using the STACK operations
smartstudent12
Assignmentdescription.pptxStep 1
Step 2
Step 3
if match
Issue an appropriate error message if ( ), { } do not match.
Processing Steps
Assignment 3
Write a java program to evaluate math expressions using the STACK operations.
You must create your own generic stack class. (do NOT use Java built-in Stack class)
Due: Friday, May 28
1
Expression Evaluation
Input math expression
Infix to Postfix
( 5 + 3 ) * ( 8 - 2 )
Postfix Evaluation
5 3 + 8 2 - *
Check ( ), { } (match/not match)
Result=48
Syntax Parsing
5 3 + 8 2 - *
( 1 + 2 ) * ( 3 - 4 )
input
Example of Processing Steps
Expression evaluation
Infix to post fix
Post fix evaluation
(OK)
1 2 + 3 4 - *
-3
( 1 + 2 } * ( 3 - 4 )
input
Post fix evaluation
( 1 + 2 } * ( 3 - 4 )
^ ( expected
in the case of “valid expression”
in the case of “invalid expression”
(stop)
(stop)
Expression evaluation
Infix to post fix
(1 + 3) * {2 - 1)
Sample output (test 5 Math expressions)
(1 + 3) * (2 – 1)
^ } expected
Answer = 4
(1 + 3 * (2 – 1)
^ ) expected
1 + 3) * (2 – 1)
^ can’t close )
(1 + 3) * (2 – 2)
Answer = 0
3
Submit 2 files
Stack211
(Generic Stack)
Main
(test 5 Math expressions)
Stack
Step 1
Step 2
Step 3
Required Stack Operations
5
Expression Evaluation
Push (, {
Infix to Postfix
push
Postfix Expression Evaluation
push
Pop ), }
isEmpty ?
pop
preference
pop
read value (top)
Java provides built-in object type called Stack. It is a collection that is based on the last in first out (LIFO) principle. On Creation, a stack is empty.
Stack Class in Java
Stack st = new Stack();
st.push(42);
int p=st.pop();
…
For the assignments, DO NOT USE Java built-in Stack.
Stack211
Stack211 myStack = new Stack211();
Create your own stack for all the steps
7
Expression Evaluation
push ‘(‘ ‘{‘
Infix to Postfix
push (+ - * /)
Postfix Expression Evaluation
push (number)
pop ‘)’ ’}’
isEmpty
pop(+ - * /)
preference
pop ( two numbers)
read value (top)
Issues on Step 1
How to create a stack
How to read a token
How to push a cha
How to pop and return
How to check “Pair”
How to handle error messages
public char[] myStack =new char[40];
39
30
…
1
0
stackTop = -1;
(We may use ArrayList)
Stack is implemented using an array
Initial value,
-1 means empty.
PUSH
POP
public void Push(char c){
stackTop ++;
myStack[stackTop]=c;
}
public char Pop(){
. . .
return c;
}
public char[] myStack =new char[40];
public boolean isEmpty(){
if (stackTop<0) { return true;}
else return false;
}
10
public class Stack211 {
static int stackTop; static char[] myStack =new char[40]; // may use ArrayList Stack211(){ // constructor stackTop = -1; } public void push(char c){ stackTop ++;
myStack[statcTop]=c;
} public char pop(){ .
.
return c;
}
public boolean isEmpty(){
}
Stack211 overall structure
for (int i = 0; i < Statement.length; i++){ // number of statements to be evaluated Stack211 st = new Stack211();
for (int j = 0; j < Statement[i].length(); j++){ // read one token by one
char c= Statement[i].charAt(j);
if ….
}
}
How to read Math expression (in Main program)
static String[] Statement = {"( 1 + 3 } * ( 2 - 1 )“, {"( 1 + 3 ) * ( 2 * 1 )“,,};
Total five math expressions
Create your own 5 math expressions
for (int i = 0; i < Statement.length; i++){ // statements to be evaluated Stack211 st = new Stack211();
for (int j = 0; j < Statement[i].length(); j++){ // read one token by one
char c= Statement[i].charAt(j);
if ( c == '(' || c == '{'){ st.push(c);
}
}
How to push a token (, { to the stack (in Main program)
static String[] Statement = {"( 1 + 3 } * ( 2 - 1 )“, {"( 1 + 3 ) * ( 2 * 1 )“,,};
for (int j = 0; j < Statement[i].length(); j++){ // read one token by one
char c= Statement[i].charAt(j);
. . .
if ( c == ‘)’ { char popC= st.pop();
if (popC !=‘(‘) {
System.out.println(“ ERROR: . . . expected “);
}
}
if ( c == ‘}’ { char popC= st.pop();
if (popC !=‘{‘) {
System.out.println(“ ERROR: . . . expected “);
}
} }
How to pop/check pair if input token is ), } (in Main program)
static String[] Statement = {"( 1 + 3 } * ( 2 - 1 )“, {"( 1 + 3 ) * ( 2 * 1 )“,,};
Let’s make more better program using the HashMap Data structure
if ( c == ‘)’ { char popC= st.pop();
if (popC !=‘(‘) {
System.out.println(“ ERROR: . . . expected “);
}
}
static HashMap<Integer, String> errorMessage = new HashMap<>(); static HashMap<Character, Character> pair = new HashMap<>();
OK
Better
How to use HashMap
static HashMap<Integer, String> errorMessage = new HashMap<>(); // error messages static HashMap<Character, Character> pair = new HashMap<>(); // )==(, }=={
public static void setErrorMessage(){ errorMessage.put(1, "Syntax Error: ) expected");
errorMessage.put(2, "Syntax Error: ( expected"); . . . }
public static void setPair(){
pair.put(‘)', ‘(’);
pair.put(‘}’, ‘{’);
. . .
}
Initialization
key
value
key
value
public static void printError(int location, int errorNo){ // print some empty spaces
for (int i=0; i<location; i++) {
print(“ “);
}
// print error mark System.out.println("^");
//print an error message using errorMessage.get(errorNo) println(errorMessage.get(errorNo));
}
Eg)
((1 + 2 ) * 3
^ ) expected
How many spaces
if(popC != pair.get(c)) {
printError(j, 1);
}
for (int j = 0; j < Statement[i].length(); j++){
char c= Statement[i].charAt(j);
if ( c == ‘)’ { char popC= st.pop();
if (popC !=‘(‘) {
System.out.println(“ ERROR: . . . expected “);
}
}
}
Stack for Char ( {
Stack for Char + - * /
Stack for integer
more about Stack211
Character
Integer
Should we create two different stacks?
20
Expression Evaluation
push
Infix to Postfix
push
Postfix Expression Evaluation
push
pop
isEmpty
pop
preference
pop
read value (top)
public class Stack211 { public int stackTop; public char[] myStack =new char[40]; Stack211(){ stackTop = -1; } public void push(char c){
} public char pop(){
}
..
Stack for Char (Step 1 & 2)
public class Stack211 { public int stackTop; public int[] myStack =new int[40]; Stack211(){ stackTop = -1; } public void push(int i){
} public int pop(){
}
..
Stack for int (Step 3)
These are the same except “Data Type”.
public static double triArea(double x1, double x2){
double area = x1 * x2 /2.0;
return area;
}
public static void main(String[] args) {
double Width = 10.0;
double Height = 5.0;
double tri = triArea(Width, Height);
System.out.println("The tri area is " + tri);
}
Parameter Passing (Just value)
Recall CS210
public class Stack211 { public int stackTop; public char[] myStack=new char[40]; Stack211(){ stackTop = -1; } public void push(char c){ stackTop++; myStack[stackTop] = c; } public char pop(){ char c = myStack[stackTop]; stackTop--; return c; }
..
double
Pass any data type you want to use
String
integer
char
Way to solve
public class Stack211 { public int stackTop; public char[] myStack=new char[40]; Stack211(){ stackTop = -1; } public void push(char c){ stackTop++; myStack[stackTop] = c; } public char pop(){ char c = myStack[stackTop]; stackTop--; return c; }
..
static void main(String[] args){
Stack211 st = new Stack211();
add function to receive data (object) type.
add function to send data (object) type.
public class Stack211 { int stackTop; char[] myStack=new char[40]; Stack211(){ stackTop = -1; } public void push(char c){ stackTop++; myStack[stackTop] = c; } public char pop(){ char c = myStack[stackTop]; stackTop--; return c; }
..
public class Stack211 <T>{ int stackTop; ArrayList <T>myStack = new ArrayList <T> ();
Stack211(){ stackTop = -1; } public void push(T c) { stackTop++; myStack.add(c); } public T pop() { T c = myStack.remove(stackTop); stackTop--; return c; }
Generic
Normal
Do not fix data type
Prepare to receive data type
Generic Stack 211
public class Stack211 <T> { public int stackTop; public ArrayList <T> myStack = new ArrayList <T> (); Stack211() { stackTop = -1; } public void push(T c) { stackTop++; myStack.add(c); } public T read() { T c = myStack.get(stackTop); return c; }
public T pop() { T c = myStack.remove(stackTop); stackTop--; return c; }
if you want to use array, modify the code a little bit.
Stack211<String> stringStack= new Stack211<>(); stringStack.push("Kpop"); String s= stringStack.pop(); System.out.println(s); Stack211<Character> charStack= new Stack211<>(); charStack.push('K'); char c= charStack.pop(); System.out.println(c); Stack211<Integer> integerStack= new Stack211<>(); integerStack.push(5); int num= integerStack.pop(); System.out.println(num);
public static void main(String[] args){
Kpop K 5
Example of using generic stack
static HashMap<Integer, String> errorMessage = new HashMap<Integer, String>();
static HashMap<Character, Character> pair = new HashMap<Character, Character>();
static String[] Statement = { ") 1 + 3 } * ( 2 - 1 )", "(1 + 3)", "{1 + 2)",..};
public static void main(String[] args) {
loadErrorMessages(); // initializes the error methods and pairs
loadPair();
More detail of each step
for (int i = 0; i < Statement.length; i++) {
String expression = Statement[i]; // creates variable for the first statement
Stack211<Character> st = new Stack211(); // creates stack from generic stack class
for (int j = 0; j < expression.length() && correct; j++) {
char c = expression.charAt(j); // sets a variable for number j character in
statement
if (c == '(' || c == '{‘) {
st.push(c); // push the char to the stack
}
if (c == ')' || c == '}') { // if the character is a right bracket
Boolean correct=testBrackets(c, j, st); // it will send to a method the
char, location, and stack
. . .
Step 1:
infix -> postfix
static String post="";
for (int i = 0; i < Statement.length; i++){ // no of statements to be evaluated
String post="";
Stack211<Character> st = new Stack211();
for (int j = 0; j < Statement[i].length(); j++){
char c= Statement[i].charAt(j);
if (c >='0' && c<='9') {post+=c;} // number?
if (c==‘)’ ||(c==‘}’) { post += pop until ‘(‘ or ‘{‘ }
if (c=='+' || c==‘-' || c=='*'|| c==‘/’) { // operator? push or pop
check priority (use hashMap)
if c is higher, push(c);
if c is lower, {
post += pop until pop is same as c’s priority
push(c)}
}
}
post+=pop till the stack is empty
// end of first statement(1 + 2 ) * 3. Postfix is now produced
}
More detail of each step
Step 2:
// eg) postfix = 1+2*3
Stack211<Integer> intSt = new Stack211(); // generic stack (Integer)
for (int k = 0; k < post.length(); k++){
char c= post.charAt(k);
if (c >='0' && c<='9'){
int value = c-'0';
// push value
}
if (c=='+' || c=='-'|| c=='*'|| c=='/') {
// pop two values
// calculate
// push back
}
} // end of evaluation
// pop
System.out.println(“result= " + pop);
postfix evaluation
More detail of each step
Step 3:
//precedence
static int precedence(char a){
if(a==‘*’) {return 2;} else if(a=='/’) (return 2;} else if(a==‘-’) (return 1;} else if(a=='+') (return 1;} else return 0; }
Primitive people did this way.
How to check the priority of two operators (for Step 2)
31
static HashMap<Character, Integer> precedence = new HashMap<>(); public static void main(String[] args) {
setPrecedence(); char iAm='*'; // iAm=infix(i).charAt(j) char pop='+'; // pop=st.pop();
if (precedence.get(iAm)>precedence.get(pop)){ System.out.println("I am higher than pop."); } else System.out.println("Pop is higher than I."); }
in 2021 …CS211 Students do…
I am higher than pop.
public static void setPrecedence(){ precedence.put('*',2); precedence.put('/',2); precedence.put('+',1); precedence.put('-',1); }
32
