Objectives: To gain experience with the Stack Data Structure and the library - s
ID: 3861719 • Letter: O
Question
Objectives:
To gain experience with the Stack Data Structure and the library - so use as many generic algorithms as possible.
Documentation:
Explain the purpose of the program as detail as possible - 8%.
Develop a solution for the problem and mention algorithms to be used -12%
List data structures to be used in solution. - 5%.
Give a description of how to use the program and expected input/output - 5%
Explain the purpose of each class you develop in the program. - 5%.
Programming:
For each method, give the pre and post conditions and invariant, if any - 10%
Program execution according to the requirements given 50%
Naming of program as required 5%
Print out of source code 5%
Description of Program
You are to write a program name calc.java that evaluates an infix expression entered by the user. The expression may contain the following tokens:
(1) Integer constants (a series of decimal digits).
(2) x (representing a value to be supplied later).
(3) Binary operators (+, -, *, / and %).
(4) Parentheses
Spaces between tokens are allowed but not required. The program will convert the expression to postfix (RPN) form and display the converted expression. The program will repeatedly prompt the user for the value of x, displaying the value of the expression each time. When the user enters the letter q instead of a number, the program terminates.
The following example illustrates the behavior of the program (user input is in bold and red):
Porgram output is in bold and green.
Enter infix expression: (x + 1) * (x – 2) / 4
Converted expression: x 1 + x 2 - * 4 /
Enter value of x: 5
Answer to expression: 4
Enter value of x: 7
Answer to expression: 10
Enter value of x: q
If the infix expression contains an error of any kind, the program must display the message Error in expression (with an optional explanation) and then terminate. The following examples illustrate various types of errors:
Enter infix expression: 1 2 +
Error in expression!! No operator between operands. Also last token must be an operand.
Enter infix expression: 10.4
Error in expression!! Cannot accept floating point numbers.
Enter infix expression: 1 ( + 2)
Error in expression!! No operator between operand and left parentheses.
Enter infix expression: 5 – (x – 2))
Error in expression!! No matching left parentheses for a right parentheses.
Enter infix expression: 1 ** 2
Error in expression!! The * operator cannot be preceded by a * operator.
The output of your program must match the format illustrated in this example.
Here are some other additional requirements for this program:
(1) You must use stack objects during the translation from infix to postfix and during the evaluation of the postfix expression.
(2) Operators must have the correct precedence and associativity.
What to turn in:
1. All of the .java and the .class/jar files at the iCollege website in the Dropbox folder for A#4 no later than 11:00 p.m. on the due date of 3/14/17
Hints:
1. Do the program in stages. First, get the infix to postfix conversion working for binary operators. Next, implement the evaluation of the postfix expression. Finally, add code to check the infix expression for errors. Use the examples from the hand out as a starting point for the program, but keep in mind that this code does not handle associativity properly. Also, it is made up of a mixture of Java and C++ syntax.
2. To detect errors in the infix expression, you will need to check for several situations:
A binary operator is preceded by an operator or an operand is preceded by an
operand.
An illegal character is encountered (such as a period).
The last token in the expression is not an operand or a right parentheses
There is no left parentheses anywhere in the stack when a right parentheses is
encountered.
The stack contains a left parenthesis when the expression ends.
3. Use a string to store the postfix expression. Use a stack of characters
during the translation from infix to postfix.
4. Use the Scanner class to read the input string and extract each token. Careful when you are reading an unknown (eg. x) from the input expression.
Need Help in Java Data Structure. Please show results
Explanation / Answer
/
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
public class calculator {
public static void main(String args[]){
// Created a Stack - ADT
Stack<Character> myStack = new Stack<Character>();
ArrayList<Character> myArray = new ArrayList<Character>();
// Boolean statements
boolean lastOperator = false;
boolean lastOpenParen = false;
boolean lastClosedParen = false;
boolean lastInt = false;
boolean prevToken = false; // if prev token was an operand
// Scanner for user input
Scanner sc = new Scanner(System.in);
// User infix input
System.out.println("Enter infix expression (q to quit): ");
String infixString = sc.nextLine();
char infix[] = infixString.toCharArray();
// Error Message - No operator between operands
if(infix[infix.length-1] == '/' || infix[infix.length-1] == '*' || infix[infix.length-1] == '%' ||
infix[infix.length-1] == '+' || infix[infix.length-1] == '-'){
System.out.println("Error in expression! No operator between operands. " +
"Also last token must be an operand or closed parenthesis.");
System.exit(-1);
}
// Error Message - No operands or open parenthesis before operator
if(infix[0] == '/' || infix[0] == '*' || infix[0] == '%' || infix[0] == '+' || infix[0] == '-'){
System.out.println("Error in expression! First token must be an"
+ " operand or open paranthesis.");
System.exit(-1);
}
//infixString = infixString;
for(int i = 0; i < infixString.length(); i++){
if(infix[i] == ' '){
continue;
}
infix[i] = infixString.charAt(i);
switch(infix[i]){
// INTEGERS
case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8':
case '9': case '0':
if(lastClosedParen){
System.out.println("Error in expression! An integer cannot directly"
+ " follow a closed parenthesis.");
System.exit(-1);
}
// if(lastInt){
// System.out.println("Error in expression! An integer cannot directly"
// + " follow another integer.");
// System.exit(-1);
// }
lastOperator = false;
lastOpenParen = false;
lastClosedParen = false;
lastInt = true;
myArray.add(infix[i]);
break;
// SPACES
case ' ': continue;
// X VARIABLE - with user input - no non-integers allowed to be inputed
case 'x':try{
System.out.println("Enter value of x: ");
int xVarInt = sc.nextInt();
String xVar = Integer.toString(xVarInt);
myArray.add(xVar.charAt(0));
} catch(InputMismatchException e){
System.out.println("Error in exception! The x variable must be an integer!");
System.exit(-1);
}
break;
// UNARY OPERATORS & BINARY OPERATORS
case '+': case '/':
case '%':
if (lastOperator){
System.out.println("Error in expression! An operator cannot"
+ " directly follow another operator.");
System.exit(-1);
}
if (lastOpenParen){
System.out.println("Error in expression! An operator cannot"
+ " directly follow an open parenthesis.");
System.exit(-1);
}
lastOperator = true;
lastOpenParen = false;
lastClosedParen = false;
lastInt = false;
while(!myStack.isEmpty() && myStack.peek() != '(' &&
precedence(infix[i]) <= precedence(myStack.peek())){
myArray.add(myStack.pop());
}
myStack.push(infix[i]);
break;
case '*':
// if (lastOpenParen){
// System.out.println("Error in expression! An operator cannot"
// + " directly follow an open parenthesis.");
// System.exit(-1);
// }
// lastOperator = true;
// lastOpenParen = false;
// lastClosedParen = false;
// lastInt = false;
try{
while(!myStack.isEmpty() && myStack.peek() != '(' &&
precedence(infix[i]) <= precedence(myStack.peek())){
myArray.add(myStack.pop());
}
myStack.push('*');
break;
} catch(EmptyStackException e){
System.out.println("Error in expresion! The * operator cannot be preceded by a * operator.");
System.exit(-1);
}
// while(myStack.peek() != '*'){
// myArray.add('*');
// }
// myStack.push('*');
// break;
// } catch(EmptyStackException e){
// System.out.println("Error in expresion! The * operator cannot be preceded by a * operator.");
// System.exit(-1);
// }
case '-': while(!myStack.isEmpty() && myStack.peek() != '(' &&
precedence(infix[i]) <= precedence(myStack.peek())){
myArray.add(myStack.pop());
}
myStack.push('-');
break;
// PARENTHESIS
case '(': myStack.push(infix[i]);
lastOperator = false;
lastOpenParen = true;
lastClosedParen = false;
lastInt = false;
break;
case ')': if(lastOperator){
System.out.println("Error in expression! A closed parenthesis"
+ " cannot directly follow an operator.");
System.exit(-1);
}
lastOperator = false;
lastOpenParen = false;
lastClosedParen = true;
lastInt = false;
try{
while(myStack.peek() != '('){
myArray.add(myStack.pop());
}
myStack.pop();
break;
} catch(EmptyStackException e){
System.out.println("Error in expression! No matching left parentheses for"
+ " a right parentheses.");
System.exit(-1);
}
// NO FLOATING POINT NUMBERS
case '.': System.out.println("Error in expression! Cannot "
+ "accept floating point numbers.");
System.exit(-1);
// QUIT - Q
case 'q': case 'Q':
System.out.println("Shutting down . . .");
System.out.println("Goodbye!");
System.exit(-1);
// DEFAULT CASE - if not binary, unary, or parentheses - illegal character
default:
System.out.println("Illegal character used. Please try again."); break;
} // End Switch
} // End For-Loop
while(!myStack.isEmpty()){
if(myStack.peek() == '('){
System.out.println("Error in expression! No matching right parenthesis for"
+ " left parentehesis");
System.exit(-1);
}
myArray.add(myStack.pop());
}
System.out.print("Converted Expression: ");
for(int i = 0; i < myArray.size(); i++){
System.out.print(myArray.get(i));
}
System.out.println();
System.out.println("Answer to Expression: " + postFixEvaluation(myArray));
} // End Main
// PRECONDITION: Takes in a char variable to check for precedence - if - then return 2 else return 1
// POSTCONDITION: Returns 2 for higher precedence if its a / % or * - Returns 1 if anything else
// Heirarchy of operators
public static int precedence(char a){
if(a == '/' || a == '%' || a == '*'){
return 2;
} else
return 1;
}
// PRECONDITION: Takes in an Arraylist of Characters
// POSTCONDITION: Returns values calculated by each case depending on user input
// Post fix stack evaluation
public static int postFixEvaluation(ArrayList<Character> a){
Stack <Integer> evaluateStack = new Stack <Integer> ();
for(int i = 0; i < a.size(); i++){
if(Character.isDigit(a.get(i))){
evaluateStack.push(Character.getNumericValue(a.get(i)));
} else{
int second = evaluateStack.pop();
int first = evaluateStack.pop();
switch(a.get(i)){
case '+': evaluateStack.push(first + second); break;
case '-': evaluateStack.push(first - second); break;
case '*': evaluateStack.push(first * second); break;
case '/': evaluateStack.push(first / second); break;
case '%': evaluateStack.push(first % second); break;
}
}
}
return evaluateStack.pop();
}
} // End Class
sample output
Enter infix expression (q to quit):
(x + 1)*(x-2)/ 4
Enter value of x:
5
Enter value of x:
5
Converted Expression: 51+52-*4/
Answer to Expression: 4
---------------------------------------------
Enter infix expression (q to quit):
1 2+
Error in expression! No operator between operands.
Also last token must be an operand or closed parenthesis.
---------------------------------------------
Enter infix expression (q to quit):
10.4
Error in expression! Cannot accept floating point numbers.
---------------------------------------------
Enter infix expression (q to quit):
1( +2)
Error in expression! An operator cannot directly follow an open parenthesis.
---------------------------------------------
Enter infix expression (q to quit):
5-(x-2))
Enter value of x:
5
Error in expression! No matching left parentheses for a right parentheses.
---------------------------------------------
Enter infix expression (q to quit):
1**2
Error in expression! An * operator cannot be preceded by another * operator.
---------------------------------------------
Enter infix expression (q to quit):
x + 5 - 2 * 5
Enter value of x:
1
Converted Expression: 15+25*-
Answer to Expression: -4
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.