Homework SourseThe concept of stack is extremely important in computer scie
The concept of stack is extremely important in computer science and is used in a wide variety of problems. This assignment requires you to write a program that can be used to evaluate ordinary arithmetic expressions that contains any of the five arithmetic operators (+, -, *, /, %).
This exercise requires three distinct steps, namely:-
Verify that the infix arithmetic expression (the original expression), that may contain regular parentheses, is properly formed as far as parentheses are concerned.
If the parenthesized expression is properly formed, convert the expression from an infix expression to its equivalent postfix expression, called Reverse Polish Notation (RPN) named after the Polish Mathematician J. Lukasiewics.
Evaluate the postfix expression, and print the result.
Step 1 - Verify that the expression
Given an arithmetic expression, called an infixed expression, to verify that it is properly formed as far as parentheses are concerned, do the following:
Create an empty stack to hold left parenthesis ONLY.
Scanned the arithmetic expression from left to right, one character at a time.
While there are more characters in the arithmetic expression
{
If the character is a left parenthesis ‘(‘, push it on to the stack. However if the character is a right parenthesis, ‘)’, visit the stack and pop the top element from off the stack.
}
If the stack contains any element at the end of reading the arithmetic expression, then the expression was not properly formed.
Step 2 - Convert infixed expression to postfix
Given that an arithmetic expression is properly form with respect to parentheses, do the following:
Create an empty stack to hold any arithmetic operators and left parenthesis, ONLY.
A string to contain the postfix expression – the output from this conversion.
Scan the arithmetic expression from left to right.
While the are more symbols in the arithmetic expression,
{
After a symbol is scanned, there are four (4) basic rules to observed and apply accordingly:
If the symbol is an operand (a number), write it to the output string.
If the symbol is an operator and if the stack is empty, push the symbol on the stack.
Otherwise, if the symbol is either ‘(‘ or ‘)’, check for the following conditions:
If the symbol is ‘(‘, push on to the stack,
Otherwise
If the symbol is ‘)’
{
Pop everything from the operator stack down to the first ‘(‘. Write each item
popped from the stack to the output string. Do not write the item ‘)’. Discard it.
}
If the symbol scanned is an arithmetic operator, check for the following and apply accordingly:
If the operator on the top of the stack has higher or equal precedence, that operator is popped from off the stack, and is written to the to the output string. This process is continues until one of two things happen:
Either the first ‘(‘ is encountered. When this occurs, the ‘(‘ is removed from the stack and is discarded, and the recently scanned symbol is placed on the stack
OR
The operator on the stack has lower precedence than the one just scanned. When this situation arises, the recently scanned symbol is pushed onto the stack.
}
4. After the arithmetic expression is exhausted, any operator is remaining on the stack must be popped from off and is written to the output string.
Step 3 - Evaluate the post fixed expression
Initialize an empty stack.
While there are more symbols in the postfix string
{
If the token is an operand, push it onto the stack.
If the token is an operator
{
Pop the two topmost values from the stack, and store them in the order t1, the topmost, and t2 the second value.
Calculate the partial result in the following order t2 operator t1
Push the result of this calculation onto the stack.
NOTE: If the stack does not have two operands, a malformed postfix expression has occurred, and evaluation should be terminated.
}
}
When the end of the input string is encountered, the result of the expression is popped from the stack.
NOTE: If the stack is empty or if it has more than one operand remaining, the result is unreliable.
Extend this algorithm to include square brackets and curly braces. For example, expressions of the following kind should be considered:
2 + { 2 * ( 10 – 4 ) / [ { 4 * 2 / ( 3 + 4) } + 2 ] – 9 }
2 + } 2 * ( 10 – 4 ) / [ { 4 * 2 / ( 3 + 4) } + 2 ] – 9 {
NOTE: The following patterns form valid parenthesizations:
( )
{ }
[ ]
[ ( ) ]
{ ( ) }
[ { ( ) } ]
All other forms are invalid.
Implement the above two algorithms for the following binary operators: addition +, subtraction -, multiplication *, division /, and modulus operation %. All operations are integer operations. To keep things simple, place at least one blank space between each token in the input string.
Solution
Driver.java
import java.io.IOException;
import java.io.DataInputStream;
public class Driver {
public static void main(String[] args) {
// TODO Test the stack
ArithmeticExpressionConversions entry = new ArithmeticExpressionConversions();
String in = getData(\"Please enter a mathematical operation. -1 to quit: \");
/*
* Loop until the user enters -1 to exit the program
*/
while (in.compareTo(\"-1\") != 0 ) {
if (entry.processEntry(in)) {
/*
* The string entered is cleaned up, spaces removed, etc.
*/
System.out.print(\"Entry processed: \");
entry.printInput();
/*
* Entry is converted to Postfixed notation and displayed
*/
System.out.println(\"Entry converted to postfix: \" + entry.convertInfixToPostfix());
System.out.print(\"Entry converted to: \");
entry.printPostString();
/*
* The Postfixed entry is evaluated and the answer displayed
*/
int answer = entry.evaluatePostfixExpression();
System.out.println(\"The answer is \" + String.valueOf(answer));
}
in = getData(\"Enter another mathematical operation. -1 to quit: \");
}
}
/*
* This method is a generic method to retrieve user input as a string
*/
public static String getData(String prompt) {
System.out.print(prompt);
String data = \"\";
DataInputStream mykb = new DataInputStream(System.in);
try {
data = mykb.readLine();
} catch (IOException e) {
System.out.println(\"Entry not valid.\");
}
return data;
}
}
ArithmeticExpressionConversions.java
public class ArithmeticExpressionConversions {
/**
* input stores the re-formatted user input, stored as a string to handle any character
*/
private String[] input;
/**
* Creates a stack used to convert infixed notation to postfixed
*/
private Stack postStack;
/**
* Holds postfixed entries
*/
private String[] postString;
/**
* Default Constructor
*/
public ArithmeticExpressionConversions() {
this(50);
}
/**
* Full Constructor
* @param input
* @param postStack
* @param postString
*
*/
public ArithmeticExpressionConversions(int s) {
input = new String[s];
postStack = new Stack(s);
postString = new String[s];
}
/**
* Converts an infixed string array to a postfixed string array
* @return
*/
public boolean convertInfixToPostfix() {
int i = 0;
int j = 0;
while (input[i] != null) {
if (input[i].compareTo(\"+\") == 0
|| input[i].compareTo(\"-\") == 0
|| input[i].compareTo(\"*\") == 0
|| input[i].compareTo(\"/\") == 0
|| input[i].compareTo(\"(\") == 0) {
postStack.push(input[i]);
} else if (input[i].compareTo(\")\") == 0) {
boolean repeat = true;
String comp = (String) postStack.peek();
while (comp.compareTo(\"(\") != 0) {
postString[j] = (String) postStack.pop();
comp = (String) postStack.peek();
j++;
}
postStack.pop();
} else {
postString[j] = input[i];
j++;
}
i++;
}
String holder;
while (postStack.getTop() != -1) {
holder = (String) postStack.pop();
if (holder.compareTo(\"(\") != 0) {
postString[j] = holder;
j++;
}
}
return true;
}
public int getValue(String s) {
if (s.compareTo(\"+\") == 0) { return 1; }
if (s.compareTo(\"-\") == 0) { return 1; }
if (s.compareTo(\"/\") == 0) { return 2; }
if (s.compareTo(\"*\") == 0) { return 2; }
else { return 3; }
}
/**
* Calculates the value of a postfixed string array
* @return
*/
public int evaluatePostfixExpression() {
int value1;
int value2;
Stack evalStack = new Stack(50);
int i = 0;
while (postString[i] != null) {
if (postString[i].compareTo(\"+\") == 0) {
value1 = Integer.parseInt(evalStack.pop().toString());
value2 = Integer.parseInt(evalStack.pop().toString());
evalStack.push(value2 + value1);
} else if (postString[i].compareTo(\"-\") == 0) {
value1 = Integer.parseInt(evalStack.pop().toString());
value2 = Integer.parseInt(evalStack.pop().toString());
evalStack.push(value2 - value1);
} else if (postString[i].compareTo(\"*\") == 0) {
value1 = Integer.parseInt(evalStack.pop().toString());
value2 = Integer.parseInt(evalStack.pop().toString());
evalStack.push(value2 * value1);
} else if (postString[i].compareTo(\"/\") == 0) {
value1 = Integer.parseInt(evalStack.pop().toString());
value2 = Integer.parseInt(evalStack.pop().toString());
evalStack.push(value2 / value1);
} else {
evalStack.push(postString[i]);
}
i++;
}
return Integer.parseInt((evalStack.pop()).toString());
}
/**
* Takes user input and either formats it or informs user of first found error
* @param n
* @return
*/
public boolean processEntry(String n) {
String[] test = {\"0\", \"1\", \"2\", \"3\", \"4\", \"5\", \"6\", \"7\", \"8\", \"9\", \"0\", \"+\", \"-\", \"*\", \"/\", \"(\", \")\"};
int balance = 0;
int index = 0;
boolean intFlag = false;
for (int i = 0; i < n.length(); i++) {
for (int j = 0; j <= test.length; j++) {
if (j > 10) {
intFlag = false;
}
if (n.substring(i, i + 1).compareTo(\" \") == 0) {
break;
}
if (j >= 17) {
System.out.print(\"Entry validity check: False - improper character: \'\");
System.out.println(n.charAt(i) + \"\'\");
return false;
}
if (n.substring(i, i + 1).compareTo(test[j]) == 0) {
if (j == 15) {
balance++;
}
if (j == 16) {
balance--;
}
if (intFlag) {
input[index - 1] = input[index - 1] + test[j];
} else {
input[index] = test[j];
index++;
if (j < 11) {intFlag = true;}
}
break;
}
}
}
if (balance == 0) {
System.out.println(\"Entry validity check: True\");
return true;
} else {
System.out.println(\"Entry validity check: False - Parenthesis unbalanced\");
return false;
}
}
/**
* Provides a method to compare strings to one another
* @param targetKey
* @return
*/
public int compareTo(Object targetKey) {
String tKey = (String) targetKey;
return (this.compareTo(tKey));
}
/**
* Displays what the user entered but reformatted
*/
public void printInput() {
for (int i = 0; i < input.length; i++) {
if (input[i] != null) {
System.out.print(input[i]);
}
}
System.out.println();
}
public boolean matchTest(String s) {
String[] test = {\"0\", \"1\", \"2\", \"3\", \"4\", \"5\", \"6\", \"7\", \"8\", \"9\", \"0\"};
for(int i = 0;i < test.length;i++) {
if(s.compareTo(test[i]) == 0) {
return true;
}
}
return false;
}
/**
* Displays postfixed string array
*/
public void printPostString() {
int i = 0;
while (postString[i] != null) {
System.out.print(postString[i] + \" \");
i++;
}
System.out.println();
}
/**
* Sets a value in the entry array
* @param n
* @param i
*/
public void setEntry(String n, int i) {
input[i] = n;
}
/**
* Retrieves an entry in the entry array
* @param i
* @return
*/
public String getEntry(int i) {
return input[i];
}
}
Stack.java
public class Stack {
private Object[] nodes;
private int top;
private int size;
/**
* Default Constructor
*
*/
public Stack() {
this(50);
}
/**
* Full Constructor
* @param s
*/
public Stack(int s) {
top = -1;
size = s;
nodes = new Object[s];
}
/**
* Push puts an object on the top of the stack as long as there is room
* in the stack.
* @param newObject
* @return
*/
public boolean push(Object newObject) {
if(top == size - 1)
return false;
else {
top = top + 1;
nodes[top] = newObject;
return true;
}
}
/**
* Pop returns and removes the object on top of the stack as long as there
* are items in the stack.
* @return
*/
public Object pop() {
int topLoc;
if(top == -1)
return null;
else {
topLoc = top;
top = top - 1;
return nodes[topLoc];
}
}
/**
* Peek returns the top item in the stack without deleting it as long
* as there are items in the stack.
* @return
*/
public Object peek() {
int topLoc;
if(top == -1)
return null;
else {
return nodes[top];
}
}
/**
* showAll will show the entire contents of the stack without modification.
*/
public void showAll() {
for(int i = top; i >= 0; i--) {
}
}
/**
* getTop returns the value of the top of the stack.
* @return
*/
public int getTop() {return top;}
/**
* getSize returns the size of the stack.
* @return
*/
public int getSize() {return size;}
}
