Assignment: class Expression
Collaboration Solo
Complete this project only with help from UofA section Leaders and the course materials (books, presentations, code demos). Do not give your code to anyone or copy any code. Do not even look at another person's computer screen! Copying code from another person’s screen is a violation of the code of academic integrity. You may use code from Rick's book, presentations code demos, lectures, or section.
Infix and PostFix Expressions
In this Assignment, you are asked to implement a new type as a Java class named Expression. The constructor takes a string representing a simplified infix expression and can immediately inform the user of the original infix expression, its postfix equivalent, and the integer value of the either expression.
@Test
public void testAllThreeMethods() {
Expression e = new Expression("(3+4)*(5-6)/7");
assertEquals("(3+4)*(5-6)/7", e.infix());
assertEquals("34+56-*7/", e.postfix());
assertEquals(-1, e.value());
}
To reduce the complexity of this assignment, all infix expressions used to construct Expression objects are valid. No error checking required. The infix expression only consist of one of these single character tokens with no white space allowed, not even one blank space anywhere such as at the end:
· One of the ten digits: 0 1 2 3 4 5 6 7 8 9
· One ofthese five binary arithmetic operators: + - / % *
o Use the same precedence as Java with / * % higher than + -
· A left or right parentheses: ( )
Here are some example infix expressions, their postfix equivalents, and their values as integers:
Infix Postfix Value
1+2 12+ 3
1-2*3 123*- -5
(((1+2)*3)-4) 12+3*4- 5
5%2 52% 1
(4*5+6*7)*(8-9) 45*67*+89-* -62
2*(3+4*5)/(6-7) 2345*+*67-/ -46
((((9)))) 9 9
class Expression with 4 public methods
Implement a Java class named Expression that has four required methods shown here. the two private helper methods are included as method stubs so this compiles.
/**
* Use a Stack to convert infix expressions into their postfix equivalent and a
* different stack to evaluate that expression to its integer equivalent.
*
* @author YOUR NAME
*/
import java.util.Stack; // Use Java's or implement your own
public class Expression {
private String my_infix;
private String my_postfix;
private int my_value;
/**
* Construct an Expression object and set these the instance variables to the
* correct values
*
* 1) my_infix: The same as the argument infixExpression
*
* 2) my_postfix: The postfix version of infixExpression
*
* 3) my_value: The value of the infixExpression as an integer
*
* Precondition: The String argument is a valid infix expression containing only
* single digit operands 0 1 2 3 4 5 6 7 8 9 and the five binary operators * / % + 1
*/
public Expression(String infixExpression) {
my_infix = infixExpression;
my_postfix = convertToPostfix(); // Name your private helper whatever you want
my_value = valueOf(); // Name your private helper whatever u want
}
// The public methods are simple accessors because all
// of the work is done immediately when this object is constructed.
public String infix() {
return my_infix;
}
public String postfix() {
return my_postfix;
}
public int value() {
return my_value;
}
private String convertToPostfix() { // Name your private helper whatever you want
return "Under construction";
}
// Determine the integer value of the postfix expression
// This is *very* similar to Rick's Code demo from lecture (See our Code Demos page)
private int valueOf() {
return -999;
}
}
Algorithm to convert from infix to postfix
Let postfix be a String that is "" and stack be an empty Stack
For each token in the input stream {
if operand: Immediately concatenate operand to postfix
if open parentheses: Push '(' on the stack
if close parentheses: Pop stack symbols and attach to postfix until peek
is an open parentheses, then pop '('
if operator: While the stack is not empty, pop all operators as long as they
are of equal or higher precedence and the top is not '('. Concatenate each
operator from stack to postfix. Then push the current operator.
}
Pop any remaining operators from the stack, concatenating them to the postfix expression
Algorithm to evaluate a postfix expression to its integer value
Make an empty stack s
For each token (operator * - + / or single digit integers 0, 1, …9) in the infix expression {
if the token is an operand
s.push(operand)
if the token is an operator {
right = s.pop()
left = s.pop()
push the value of the operator (* - / +) applied to the left and right
}
}
Note: The value of the postfix expression is now at the top of the stack
Grading Criteria 60 pts
____+60 Web-Cat correctness and code coverage: To earn 60 points, you will need 100% code coverage and 100% problem coverage (Rick's tests pass and you exercised all methods). These 60 points are derived from Web-Cat. You may submit as many times as you wish until you have 100% on both. Notice that a multiplication feature is employed that means 90% code coverage and 90% problem coverage results in 0.9 * 0.9 * 60 for 48.6/60 points.
_____/ -60 If you did not use the Stack algorithms listed on this spec. You will receive a 0 for not using the above algorithms with stack objects. The main goal of this assignment is to learn how to use stacks to solve a very challenging problem.