Evaluate mathematical expressions

Assignment

 Your task in this assignment is to evaluate arithmetic expressions and calculate their values. The
statements are written in a programming language whose syntax is described below. You will useJava to write a parser and an evaluator for expressions written in this language. For simplicity youwill only deal with input expressions that are composed of positive integers and the operators thatare listed below.

+ addition                                               ++ increment
– subtraction                                            — decrement
* multiplication                                       [ ] absolute value
/ integer division

You may assume that values of expressions are of type intin Java and are within the range specifiedby that type. Since the subtraction operator is included in the list below, the value of an expressioncan be either positive or negative.
Increment or decrement operations on constants are not allowed in Java. But our language doesallow it. In particular, our language has the pre-increment operation which increments values ofan integers or an expression, and similarly it has the pre-decrement operation which decrementsvalues. For example, the value of “(++5)” is “6″ while expression “(–(9))” evaluates to 8.
Note that operators +, -, *, / are binary operators, i.e, they operate on two elements and produce a value, whereas the operators ++, — and [ ] are unary operators, i.e, they operate on asingle element and produce a value. Consider an expression “(++(3 + 2))” in our language. Thebinary operator “+” operates on two intvalues 2 and 3 and produces 5. The unary operator “++”then operates on the result 5, a single value, and produces 6 which is the value of the expression.
Similarly “((++(5 – 2)) + 3)” evaluates to 7.
The absolute value operator is denoted by [ ], instead of the | |which is generally used inarithmetic. We use the square brackets because they have a left and right versions which makesparsing easier. An expression within the [ ] operator evaluates to its absolute value. Note that nosuch operator exists in Java.

Formal language

Your task in this assignment is to write code to parse and evaluate expressions. You can assume thatyour code will only be tested on valid expressions. But how can we define what a valid expressionis? As you will learn if you take COMP 330 and later a compilers course such as COMP 520, thereare formal methods for defining languages. Indeed most programming languages are defined usingthese formal methods.
The syntactic rules for expressions and operators in our expression language can be defined as
follows. A digit is defined:
digit = 0 |1 |2 |9
The vertical bar |does not appear in expressions. Rather it is used here to mean or, that is, a digit
can be any one of the characters ‘0’, ‘1’,.. ‘9’. Using the definition of a digit, we can then define apositive integer in a recursive manner as follows,
positiveInteger= digit |digit positiveInteger
so a positive integer is a digit or a digit followed by a positive integer. Notice that in this definitionwe allow positive integers to start with digit ‘0’, but you can redefine a positive integer to excludethis case if we wish. We can also define operators
IncDecOperator= + + | – –
binaryOperator= + | – | |/

In a similar manner we define an expression as follows:
expression = ( positiveIntegerbinaryOperatorpositiveInteger) |
( expression binaryOperatorpositiveInteger) |
( positiveIntegerbinaryOperator expression ) |
( expression binaryOperator expression ) |
( IncDecOperatorpositiveInteger) |
( IncDecOperator expression ) |
[ expression ] |
[ positiveInteger]

An expression is therefore one of the following:
a positive integer or an expression followed by a binary operator followed by a positive integer
or an expression, enclosed within round brackets
an increment or decrement operator followed by a positive integer or by an expression, enclosedwithin round brackets.
an expression or a positive integer, enclosed within square brackets
Note that a valid expression is always contained within brackets. Thus “(3+1)” is a valid expressionbut “3+1″ is not. This requirement on the brackets ensures that there is a unique order forevaluating the (sub)expressions in the case that an expression has multiple operators. We will
return to this issue later in the course when we discuss expression trees.
In your solution, you may assume that each expression has been parenthesized with proper nesting. Therefore, you don’t need to worry about operator precedence issues nor checking for balancedparenthesis. Table 1 below lists some valid expressions and their respective values

Parsing
Your first task is to parse in input expression string into meaningful units called tokens. Parsing
will take an expression as a string and return an array list of the tokens in the expression, such
that each token is string. We use an array list because it is more efficient than a linked list in
certain situations. Thus, the expression “(27 + 572)” should be parsed into the list of five tokens:
“(“, “27″, “+”, “572″, “)”. Note that white spaces in an expression string must be ignored when
parsing.
We can then take this list of tokens as input to the eval() method. It is important that forany expressions containing the “++” and “–” operators be stored as a single token rather than as
two. Thus, “(++25)” should be parsed as “(“, “++”, “25″, “)” rather than “(“, “+”, “+”, “25″, “)”. Also note that “25″ must be not be parsed as “2″, “5″.
The parsing is done in the Expression constructor. You will need to fill in the missing code
where it is indicated.
You should use the Java StringBuilderclass to build each token as you parse the expression string. The append() and delete() methods of the StringBuilderclass will be helpful intokenizing the string.

Evaluation
The evaluation is done in the evalmethod. Again, your task is to fill in the missing code where it isindicated. The easiest approach is to use two stacks, one to store values (named valueStackin thestarter code) and another (named operatorStack) to store tokens such as operators or brackets.
We emphasize that you may assume that all expressions are valid; that is, they are syntactically
correct and will evaluate to a single value. HINT: Considering that all expressions are syntacticallycorrect, there is no need to store the opening bracket of an expression in the stacks.

Testing
We provide an additional tester class to test your expression class along with sample testing files
(sample in.txt, sample value.txt) which test for simple expressions only. Your code will be
evaluated on a much more extensive and challenging set of test cases, and we encourage you to postcomplicated test cases on the discussion board. 

Expression.java

package assignments2017.A2PostedCode;

/*

*/

importjava.util.Stack;

importjava.util.ArrayList;

public class Expression  {

privateArrayList<String>tokenList;

//  Constructor

/**

* The constructor takes in an expression as a string

* and tokenizes it (breaks it up into meaningful units)

* These tokens are then stored in an array list ‘tokenList’.

*/

Expression(String expressionString) throws IllegalArgumentException{

tokenList = new ArrayList<String>();

StringBuilder token = new StringBuilder();

//ADD YOUR CODE BELOW HERE

//..

//..

//ADD YOUR CODE ABOVE HERE

}

/**

* This method evaluates the expression and returns the value of the expression

* Evaluation is done using 2 stack ADTs, operatorStack to store operators

* andvalueStack to store values and intermediate results.

* – You must fill in code to evaluate an expression using 2 stacks

*/

public Integer eval(){

Stack<String>operatorStack = new Stack<String>();

Stack<Integer>valueStack = new Stack<Integer>();

//ADD YOUR CODE BELOW HERE

//..

//..

//ADD YOUR CODE ABOVE HERE

return null;   // DELETE THIS LINE

}

//Helper methods

/**

* Helper method to test if a string is an integer

* Returns true for strings of integers like “456”

* and false for string of non-integers like “+”

* – DO NOT EDIT THIS METHOD

*/

privatebooleanisInteger(String element){

try{

Integer.valueOf(element);

}catch(NumberFormatException e){

return false;

}

return true;

}

/**

* Method to help print out the expression stored as a list in tokenList.

* – DO NOT EDIT THIS METHOD

*/

@Override

public String toString(){

String s = new String();

for (String t : tokenList )

s = s + “~”+  t;

return s;

}

}

Tester.java

package assignments2017.A2PostedCode;

importjava.io.IOException;

importjava.io.FileReader;

importjava.io.BufferedReader;

public class Tester{

public static void main(String[] args) throws IOException {

//  You need to change your root directory.

String root = “C:\\\\Users\\\\Michael\\\\Dropbox\\\\Eclipse (Yoga)\\\\250\\\\src\\\\assignments2017\\\\A2PostedCode\\\\tests\\\\”;

String[] input = {“sample_in.txt”};

String[] output = {“sample_value.txt”};

String[] parsedExp = {“sample_exp.txt”};

/**

* Test each input file in the array of strings ‘input’

* and compare with expected output in corresponding file

* in output files listed in array of strings ‘output’

**/

for(int i = 0 ; i <input.length; i++){

String inputFileName = root + input[i];

String outputFileName = root + output[i];

String expFileName = root + parsedExp[i];

FileReader fin = new FileReader(inputFileName);

FileReaderfout = new FileReader(outputFileName);

FileReaderfexp = new FileReader(expFileName);

BufferedReaderinputReader = new BufferedReader(fin);

BufferedReaderoutputReader = new BufferedReader(fout);

BufferedReaderexpReader = new BufferedReader(fexp);

Integer passed = 0,expectedValue=0, computedValue = 0;

String expString;

String computedParsedExpression, expectedParsedExpression;

Expression exp;

/**

Test for each input test case in the input file

**/

while((expString = inputReader.readLine()) != null){

//Read expected output from the output file

expectedValue = Integer.valueOf(outputReader.readLine());

expectedParsedExpression = expReader.readLine();

//Construct Expression from expression string read from

exp = new Expression(expString);

computedParsedExpression = exp.toString();

//compare the parsed expressions

if (computedParsedExpression.equals(expectedParsedExpression)) {

passed++;

}

else{

System.out.println(“Passed ” + passed + ” tests”);

System.out.println(“Failed for input: ” + expString);

System.out.println(“Expected : ” + expectedParsedExpression);

System.out.println(“Result:   ” + computedParsedExpression);

System.exit(-1);

}

//compute the value of expression using the eval() method

computedValue = exp.eval();

//compare the values

if (computedValue.equals(expectedValue)) {

passed++;

System.out.println(exp);

//System.out.println(exp + ” = ” + computedValue);

}

else{

System.out.println(“Passed ” + passed + ” tests”);

System.out.println(“Failed for input: ” + expString);

System.out.println(“Expected : ” + expectedValue);

System.out.println(“Result:   ” + computedValue);

System.exit(-1);

}

}

System.out.println(“Passed all ” + passed + ” tests.”);

}

}

} 

Solution 

Expression.java 

package assignments2017.A2PostedCode;

/*

*/

importjava.util.Stack;

importjava.util.ArrayList;

public class Expression  {

privateArrayList<String>tokenList;

//  Constructor

/**

* The constructor takes in an expression as a string

* and tokenizes it (breaks it up into meaningful units)

* These tokens are then stored in an array list ‘tokenList’.

*/

Expression(String expressionString) throws IllegalArgumentException{

tokenList = new ArrayList<String>();

StringBuilder token = new StringBuilder();

//ADD YOUR CODE BELOW HERE

for (int i = 0; i <expressionString.length(); i++) {

char c = expressionString.charAt(i);

if (c == ‘(‘ || c == ‘)’ || c == ‘*’ || c == ‘/’ || c == ‘[‘ || c == ‘]’) {

tokenList.add(“” + c);

} else if (c == ‘+’ || c == ‘-‘) {

// check if this is ++ or —

if (i + 1 <expressionString.length() &&expressionString.charAt(i + 1) == c) {

i ++;

tokenList.add(“” + c + c);

} else {

tokenList.add(“” + c);

}

} else if (c >= ‘0’ && c <= ‘9’) { // get a whole positive integer

token.append(c);

while (i + 1 <expressionString.length()) {

c = expressionString.charAt(i + 1);

if (c >= ‘0’ && c <= ‘9’) {

token.append(c);

i ++;

} else {

break;

}

}

// add the integer into the token list

tokenList.add(token.toString());

token.delete(0, token.length());

} else if (c != ‘ ‘) {

System.out.printf(“WARNING: ingored index=%d character=%c\n”, i, c);

}

}

//ADD YOUR CODE ABOVE HERE

}

/**

* This method evaluates the expression and returns the value of the expression

* Evaluation is done using 2 stack ADTs, operatorStack to store operators

* andvalueStack to store values and intermediate results.

* – You must fill in code to evaluate an expression using 2 stacks

*/

public Integer eval(){

Stack<String>operatorStack = new Stack<String>();

Stack<Integer>valueStack = new Stack<Integer>();

//ADD YOUR CODE BELOW HERE

for (String token : tokenList) {

if (“(“.equals(token) || “[“.equals(token)) {

// nothing needs to do here

} else if (“)”.equals(token) &&operatorStack.isEmpty()) {

// nothing needs to do here

} else if (“)”.equals(token)) {

// remove one operator and corresponding operands from the stacks

String operator = operatorStack.pop();

int op2 = valueStack.pop();

// save the result back to the value stack

if (“++”.equals(operator)) {

valueStack.push(++op2);

} else if (“–“.equals(operator)) {

valueStack.push(–op2);

} else { // binary operator

int op1 = valueStack.pop();

if (“+”.equals(operator)) {

valueStack.push(op1 + op2);

} else if (“-“.equals(operator)) {

valueStack.push(op1 – op2);

} else if (“*”.equals(operator)) {

valueStack.push(op1 * op2);

} else { // if (“/”.equals(operator)) {

valueStack.push(op1 / op2);

}

}

} else if (“]”.equals(token)) {

int op = valueStack.pop();

if (op < 0) { // get the absolute value

op = -op;

}

valueStack.push(op);

} else if (isInteger(token)) { // add into the operand

valueStack.push(Integer.parseInt(token));

} else { // an operator

operatorStack.push(token);

}

}

returnvalueStack.pop();

//ADD YOUR CODE ABOVE HERE

}

//Helper methods

/**

* Helper method to test if a string is an integer

* Returns true for strings of integers like “456”

* and false for string of non-integers like “+”

* – DO NOT EDIT THIS METHOD

*/

privatebooleanisInteger(String element){

try{

Integer.valueOf(element);

}catch(NumberFormatException e){

return false;

}

return true;

}

/**

* Method to help print out the expression stored as a list in tokenList.

* – DO NOT EDIT THIS METHOD

*/

@Override

public String toString(){

String s = new String();

for (String t : tokenList )

s = s + “~”+  t;

return s;

}

}

Tester.java 

package assignments2017.A2PostedCode;

importjava.io.IOException;

importjava.io.FileReader;

importjava.io.BufferedReader;

public class Tester{

public static void main(String[] args) throws IOException {

//  You need to change your root directory.

String root = “C:\\\\Users\\\\Michael\\\\Dropbox\\\\Eclipse (Yoga)\\\\250\\\\src\\\\assignments2017\\\\A2PostedCode\\\\tests\\\\”;

String[] input = {“sample_in.txt”};

String[] output = {“sample_value.txt”};

String[] parsedExp = {“sample_exp.txt”};

/**

* Test each input file in the array of strings ‘input’

* and compare with expected output in corresponding file

* in output files listed in array of strings ‘output’

**/

for(int i = 0 ; i <input.length; i++){

String inputFileName = root + input[i];

String outputFileName = root + output[i];

String expFileName = root + parsedExp[i];

FileReader fin = new FileReader(inputFileName);

FileReaderfout = new FileReader(outputFileName);

FileReaderfexp = new FileReader(expFileName);

BufferedReaderinputReader = new BufferedReader(fin);

BufferedReaderoutputReader = new BufferedReader(fout);

BufferedReaderexpReader = new BufferedReader(fexp);

Integer passed = 0,expectedValue=0, computedValue = 0;

String expString;

String computedParsedExpression, expectedParsedExpression;

Expression exp;

/**

Test for each input test case in the input file

**/

while((expString = inputReader.readLine()) != null){

//Read expected output from the output file

expectedValue = Integer.valueOf(outputReader.readLine());

expectedParsedExpression = expReader.readLine();

//Construct Expression from expression string read from

exp = new Expression(expString);

computedParsedExpression = exp.toString();

//compare the parsed expressions

if (computedParsedExpression.equals(expectedParsedExpression)) {

passed++;

}

else{

System.out.println(“Passed ” + passed + ” tests”);

System.out.println(“Failed for input: ” + expString);

System.out.println(“Expected : ” + expectedParsedExpression);

System.out.println(“Result:   ” + computedParsedExpression);

System.exit(-1);

}

//compute the value of expression using the eval() method

computedValue = exp.eval();

//compare the values

if (computedValue.equals(expectedValue)) {

passed++;

System.out.println(exp);

//System.out.println(exp + ” = ” + computedValue);

}

else{

System.out.println(“Passed ” + passed + ” tests”);

System.out.println(“Failed for input: ” + expString);

System.out.println(“Expected : ” + expectedValue);

System.out.println(“Result:   ” + computedValue);

System.exit(-1);

}

}

System.out.println(“Passed all ” + passed + ” tests.”);

}

}

}