The second project involves completing and extending the C++ program that evalua
ID: 3912925 • Letter: T
Question
The second project involves completing and extending the C++ program that evaluates statements of an expression language contained in the module 3 case study.
The statements of that expression language consist of an arithmetic expression followed by a list of assignments. Assignments are separated from the expression and each other by commas. A semicolon terminates the expression. The arithmetic expressions are fully parenthesized infix expressions containing integer literals and variables. The valid arithmetic operators are +, –, *, /. Tokens can be separated by any number of spaces. Variable names begin with an alphabetic character, followed by any number of alphanumeric characters. Variable names are case sensitive. This syntax is described by BNF and regular expressions in the case study.
The program reads in the arithmetic expression and encodes the expression as a binary tree. After the expression has been read in, the variable assignments are read in and the variables and their values of the variables are placed into the symbol table. Finally the expression is evaluated recursively.
Your first task is to complete the program provided by providing the three missing classes, Minus, Times and Divide.
Next, you should extend the program so that it supports relational, logical and conditional expression operators as defined by the following extension to the grammar:
Note that there are a few differences in the use of these operators compared to their customary use in the C family of languages. Their differences are:
? In the conditional expression operator, the symbols are reversed and the third operand represents the condition. The first operand is the value when true and the second the value when false
? The logical operators use single symbols not double, for example the and operator is & not &&
? The negation operator ! is a postfix operator, not a prefix one
? There are only three relational operators not the usual six and the operator for equality is = not ==
Like C and C++, any arithmetic expression can be interpreted as a logical value, taking 0 as false and anything else as true
Your final task is to make the following two modifications to the program:
? The program should accept input from a file, allowing for multiple expressions arranged one per line.
? All results should be changed from double to int. In particular the evaluate function should return an int
====================Module 3 Case Study=============================================
minus.h:
//define the class Minus subclass of the SubExpression
class Minus : public SubExpression
{
public:
//define the default construtor
Minus(Expression* left, Expression* right) : SubExpression(left, right)
{
}
//define the function evaluate()
double evaluate()
{
//subtract the value of right from the value of the left
//and return the value.
return left->evaluate() - right->evaluate();
}
};
times.h:
//define the class Minus subclass of the SubExpression
class Times : public SubExpression
{
public:
//define the default construtor
Times(Expression* left, Expression* right) : SubExpression(left, right)
{
}
//define the function evaluate()
double evaluate()
{
//multiple the value of right and value of the left
//and return the value.
return left->evaluate() * right->evaluate();
}
};
divide.h:
//define the class Minus subclass of the SubExpression
class Divide : public SubExpression
{
public:
//define the default construtor
Divide(Expression* left, Expression* right) : SubExpression(left, right)
{
}
//define the function evaluate()
double evaluate()
{
//divide the value of left and value of the right
//and return the value.
return left->evaluate() / right->evaluate();
}
};
plus.h:
//define the class Plus subclass of the SubExpression
class Plus: public SubExpression
{
public:
//define the default construtor
Plus(Expression* left, Expression* right): SubExpression(left, right)
{
}
//define the function evaluate()
double evaluate()
{
//adds the value of left and value of the right
//and return the value.
return left->evaluate() + right->evaluate();
}
};
expression.h:
//define the class Expression
class Expression
{
public:
//declare a virtual function evaluate()
virtual double evaluate() = 0;
};
subexpression.h:
//define the class SubExpression subclass of the Expression
class SubExpression : public Expression
{
public:
//constructor
SubExpression(Expression* left, Expression* right);
//declare a static function parse()
static Expression* parse();
protected:
//declare the variables
Expression* left;
Expression* right;
};
operand.h:
//define the class Operand subclass of the Expression
class Operand : public Expression
{
public:
//declare a static function parse()
static Expression* parse();
};
variable.h:
#include <strstream>
#include <vector>
using namespace std;
//define the class Variable subclass of the Operand
class Variable : public Operand
{
public:
//define the construtor
Variable(string name)
{
this->name = name;
}
//define the function evaluate()
double Variable::evaluate();
private:
string name;
};
parse.h:
#include <iostream>
#include <string>
//declare a function parseName()
string parseName();
literal.h:
//define the class Literal subclass of the Operand
class Literal : public Operand
{
public:
//define the construtor
Literal(int value)
{
this->value = value;
}
//define the function evaluate()
//returns the value
double evaluate()
{
return value;
}
private:
int value;
};
symboltable.h:
//define the class SubExpression
class SymbolTable
{
public:
//constructor
SymbolTable() {}
//declare the function
void insert(string variable, double value);
double lookUp(string variable) const;
private:
//define the structure Symbol
struct Symbol
{
Symbol(string variable, double value)
{
this->variable = variable;
this->value = value;
}
string variable;
double value;
};
//create a vector of type Symbol
vector <Symbol> elements;
};
operand.cpp:
#include <cctype>
#include <iostream>
#include <list>
#include <string>
using namespace std;
#include "expression.h"
#include "subexpression.h"
#include "operand.h"
#include "variable.h"
#include "literal.h"
#include "parse.h"
//definition of the function parse()
Expression* Operand::parse()
{
char paren;
double value;
cin >> ws;
if (isdigit(cin.peek()))
{
cin >> value;
Expression* literal = new Literal(value);
return literal;
}
if (cin.peek() == '(')
{
cin >> paren;
return SubExpression::parse();
}
else
return new Variable(parseName());
return 0;
}
variable.cpp
#include <strstream>
#include <vector>
using namespace std;
#include "expression.h"
#include "operand.h"
#include "variable.h"
#include "symboltable.h"
//create an object of SymbolTable
extern SymbolTable symbolTable;
//definition of the function evaluate()
double Variable::evaluate()
{
//return the name from the symbolTable
return symbolTable.lookUp(name);
}
symboltable.cpp:
#include <string>
#include <vector>
using namespace std;
#include "symboltable.h"
//definition of the function insert()
void SymbolTable::insert(string variable, double value)
{
//push the symbol in to the vector
const Symbol& symbol = Symbol(variable, value);
elements.push_back(symbol);
}
//definition of the function lookUp()
double SymbolTable::lookUp(string variable) const
{
//search in the vector and return the value.
for (int i = 0; i < elements.size(); i++)
if (elements[i].variable == variable)
return elements[i].value;
return -1;
}
subexpression.cpp
#include <iostream>
using namespace std;
#include "expression.h"
#include "subexpression.h"
#include "operand.h"
#include "plus.h"
#include "minus.h"
#include "times.h"
#include "divide.h"
//define the constructor
SubExpression::SubExpression(Expression* left, Expression* right)
{
this->left = left;
this->right = right;
}
//definition of the class parse()
Expression* SubExpression::parse()
{
Expression* left;
Expression* right;
char operation, paren;
//read the Operand
left = Operand::parse();
//read the operation
cin >> operation;
//read the Operand
right = Operand::parse();
//read the paren
cin >> paren;
switch (operation)
{
case '+':
return new Plus(left, right);
case '-':
return new Minus(left, right);
case '*':
return new Times(left, right);
case '/':
return new Divide(left, right);
}
system("pause");
return 0;
}
parse.cpp
#include <cctype>
#include <iostream>
#include <string>
using namespace std;
#include "parse.h"
//definition of the function parseName()
string parseName()
{
char alnum;
string name = "";
cin >> ws;
while (isalnum(cin.peek()))
{
cin >> alnum;
name += alnum;
}
return name;
}
main.cpp:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#include "expression.h"
#include "subexpression.h"
#include "symboltable.h"
#include "parse.h"
//create an object of SymbolTable
SymbolTable symbolTable;
//prototype of the function
void parseAssignments();
//define main function
int main()
{
Expression* expression;
char paren, comma;
cout << "Enter expression: ";
cin >> paren;
expression = SubExpression::parse();
cin >> comma;
parseAssignments();
cout << "Value = " << expression->evaluate() << endl;
cin>>comma;
return 0;
}
//definition of the function parseAssignments()
void parseAssignments()
{
char assignop, delimiter;
string variable;
double value;
do
{
variable = parseName();
cin >> ws >> assignop >> value >> delimiter;
symbolTable.insert(variable, value);
}
while (delimiter == ',');
}
Explanation / Answer
********************************************
and.h
class And: public SubExpression
{
public:
And(Expression* left, Expression* right): SubExpression(left, right)
{
}
int evaluate()
{
return left->evaluate() && right->evaluate();
}
};
********************************************
divide.h
class Divide: public SubExpression
{
public:
Divide(Expression* left, Expression* right): SubExpression(left, right)
{
}
int evaluate()
{
return left->evaluate() / right->evaluate();
}
};
********************************************
equality.h
class Equality: public SubExpression
{
public:
Equality(Expression* left, Expression* right): SubExpression(left, right)
{
}
int evaluate()
{
return left->evaluate() == right->evaluate();
}
};
********************************************
expression.h
class Expression
{
public:
virtual int evaluate() = 0;
};
********************************************
greaterThan.h
class GreaterThan: public SubExpression
{
public:
GreaterThan(Expression* left, Expression* right): SubExpression(left, right)
{
}
int evaluate()
{
return left->evaluate() > right->evaluate();
}
};
********************************************
lessThan.h
class LessThan: public SubExpression
{
public:
LessThan(Expression* left, Expression* right): SubExpression(left, right)
{
}
int evaluate()
{
return left->evaluate() < right->evaluate();
}
};
********************************************
literal.h
class Literal: public Operand
{
public:
Literal(int value)
{
this->value = value;
}
int evaluate()
{
return value;
}
private:
int value;
};
********************************************
minus.h
class Minus: public SubExpression
{
public:
Minus(Expression* left, Expression* right): SubExpression(left, right)
{
}
int evaluate()
{
return left->evaluate() - right->evaluate();
}
};
********************************************
negation.h
class Negation: public SubExpression
{
public:
Negation(Expression* left, Expression* right): SubExpression(left, right)
{
}
int evaluate()
{
return !(left->evaluate());
}
};
********************************************
operand.cpp
#include <cctype>
#include <iostream>
#include <sstream>
#include <list>
#include <string>
using namespace std;
#include "expression.h"
#include "subexpression.h"
#include "operand.h"
#include "variable.h"
#include "literal.h"
#include "parse.h"
#include "or.h"
#include "and.h"
#include "equality.h"
#include "greaterThan.h"
#include "lessThan.h"
#include "ternary.h"
#include "negation.h"
Expression* Operand::parse(stringstream& in)
{
char paren;
int value;
in >> ws;
if (isdigit(in.peek()))
{
in >> value;
Expression* literal = new Literal(value);
return literal;
}
if (in.peek() == '(')
{
in >> paren;
return SubExpression::parse(in);
}
else
return new Variable(parseName(in));
return 0;
}
********************************************
operand.h
class Operand: public Expression
{
public:
static Expression* parse(stringstream& in);
};
********************************************
or.h
class Or: public SubExpression
{
public:
Or(Expression* left, Expression* right): SubExpression(left, right)
{
}
int evaluate()
{
return left->evaluate() || right->evaluate();
}
};
********************************************
parse.cpp
#include <cctype>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
#include "parse.h"
string parseName(stringstream& in)
{
char alnum;
string name = "";
in >> ws;
while (isalnum(in.peek()))
{
in >> alnum;
name += alnum;
}
return name;
}
********************************************
parse.h
string parseName(stringstream& in);
********************************************
plus.h
class Plus: public SubExpression
{
public:
Plus(Expression* left, Expression* right): SubExpression(left, right)
{
}
int evaluate()
{
return left->evaluate() + right->evaluate();
}
};
********************************************
subexpression.cpp
#include <iostream>
#include <sstream>
using namespace std;
#include "expression.h"
#include "subexpression.h"
#include "operand.h"
#include "plus.h"
#include "minus.h"
#include "times.h"
#include "divide.h"
#include "or.h"
#include "and.h"
#include "equality.h"
#include "greaterThan.h"
#include "lessThan.h"
#include "ternary.h"
#include "negation.h"
SubExpression::SubExpression(Expression* left, Expression* right)
{
this->left = left;
this->right = right;
}
Expression* SubExpression::parse(stringstream& in)
{
Expression* left;
Expression* right;
Expression* condition;
char operation, paren;
/* This is where the program determines which of the three tupes of <exp> needs to be built. When we get here
* we should have burnt a paren char and the next chars in has to be an operand */
left = Operand::parse(in);
// At this point the next thing in could be an <op>, or ':' or '!'
// Use a switch statement to call the correct operation
in >> operation;
if(operation == '!') {// Negation Expression
in >> paren;
return new Negation(left,NULL); //Passing a NULL as the second argument as the negation opeation really only functions on one operand
} else if(operation == ':') {//Ternary Expression
right = Operand::parse(in);
in >> paren;// this char should acutaly be a '?'
condition = Operand::parse(in);
in >> paren;
return new Ternary(left,right,condition);
} else {//Every other Expression
//These two operations need to be performed for every case that follows
right = Operand::parse(in);
in >> paren;
switch (operation)
{
case '+': return new Plus(left, right);
case '-': return new Minus(left, right);
case '*': return new Times(left, right);
case '/': return new Divide(left, right);
case '|': return new Or(left, right);
case '&': return new And(left, right);
case '=': return new Equality(left, right);
case '>': return new GreaterThan(left, right);
case '<': return new LessThan(left, right);
}
}
return 0;
}
********************************************
subexpression.h
class SubExpression: public Expression
{
public:
SubExpression(Expression* left, Expression* right);
static Expression* parse(stringstream& in);
protected:
Expression* left;
Expression* right;
};
********************************************
symboltable.cpp
#include <string>
#include <vector>
using namespace std;
#include "symboltable.h"
void SymbolTable::insert(string variable, int value)
{
const Symbol& symbol = Symbol(variable, value);
elements.push_back(symbol);
}
int SymbolTable::lookUp(string variable) const
{
for (int i = 0; i < elements.size(); i++)
if (elements[i].variable == variable)
return elements[i].value;
return -1;
}
void SymbolTable::init()
{
if(elements.size() > 0)
{
for(int i = elements.size(); i > 0; i--) {
elements.pop_back();
}
}
}
********************************************
symboltable.h
class SymbolTable
{
public:
SymbolTable() {}
void insert(string variable, int value);
int lookUp(string variable) const;
void init();
private:
struct Symbol
{
Symbol(string variable, int value)
{
this->variable = variable;
this->value = value;
}
string variable;
int value;
};
vector<Symbol> elements;
};
********************************************
ternary.h
class Ternary: public SubExpression
{
public:
Ternary(Expression* left, Expression* right, Expression* condition): SubExpression(left, right)
{
this->condition = condition;
}
int evaluate()
{
return condition->evaluate() ? left->evaluate() : right->evaluate();
}
private:
Expression* condition;
};
********************************************
times.h
class Times: public SubExpression
{
public:
Times(Expression* left, Expression* right): SubExpression(left, right)
{
}
int evaluate()
{
return left->evaluate() * right->evaluate();
}
};
********************************************
variable.cpp
#include <strstream>
#include <vector>
using namespace std;
#include "expression.h"
#include "operand.h"
#include "variable.h"
#include "symboltable.h"
extern SymbolTable symbolTable;
int Variable::evaluate()
{
return symbolTable.lookUp(name);
}
********************************************
variable.h
class Variable: public Operand
{
public:
Variable(string name)
{
this->name = name;
}
int evaluate();
private:
string name;
};
********************************************
main.cpp
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#include "expression.h"
#include "subexpression.h"
#include "symboltable.h"
#include "parse.h"
SymbolTable symbolTable;
void parseAssignments(stringstream& in);
int main()
{
const int SIZE = 256;
Expression* expression;
char paren, comma, line[SIZE];
ifstream fin("input.txt");
while(true)
{
symbolTable.init();
fin.getline(line, SIZE);
if(!fin) break;
stringstream in(line, ios_base::in);
in >> paren;
cout << line << " ";
try
{
expression = SubExpression::parse(in);
in >> comma;
parseAssignments(in);
cout << "Value = " << expression->evaluate() << endl;
} catch(exception) {
return EXIT_FAILURE;
}
}
return 0;
}
void parseAssignments(stringstream& in)
{
char assignop, delimiter;
string variable;
int value;
do
{
variable = parseName(in);
in >> ws >> assignop >> value >> delimiter;
symbolTable.insert(variable, value);
}
while (delimiter == ',');
}
********************************************
Some inputs:::
(x & y), x = 1, y = 0;
(x & y), x = 0, y = 1;
(x & y), x = 1, y = 1;
(x & y), x = -2, y = 1;
(x & y), x = -2, y = -1;
(x & (y & z)), x = 0, y = 0, z = 0;
(x & (y & z)), x = 1, y = 1, z = 1;
(x = y), x = 0, y = 0;
(x = y), x = 1, y = 0;
(x = y), x = 1, y = 1;
(x = y), x = -1, y = -1;