The second project involves completing and extending the C++ program that evalua
ID: 3579706 • 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. There 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. Some hints for accomplishing this transformation will be provided in the conference
All results should be changed from double to int. In particular the evaluate function should return an int.
You may assume that all input to the program is syntactically correct.
You are to submit the source code for the entire program in a .zip file. Your program must compile with Microsoft Visual C++ or any modern C/C++ compiler on your O/S.
Module 3 case study:
An Expression Interpreter
The case study for this module incorporates two of the language features that we discussed—expressions and assignments. The program interprets fully parenthesized arithmetic expressions that contain either literal values or variables. The variables must then subsequently be assigned values.
The grammar for the language that this interpreter accepts is defined by the following grammar:
The regular expressions defining the three tokens are the following:
So, if you were to enter the following expression:
the interpreter would respond:
The interpreter itself is written in C++. The complete program consists of 10 classes. We will present 7 of them. Your instructor may ask you to complete this program, perhaps enhance it, and add some error checking as one of the programming projects.
We begin with the main function and one subordinate function, which are contained in module3.cpp. The main function reads in the program, calls upon the static function parse of the SubExpression class to parse it, and builds an arithmetic expression tree. It then calls the subordinate function parseAssignments to parse the assignments and enter them into the symbol table, and then evaluates the expression and displays the result. That code is shown below:
The arithmetic expression tree is built using an inheritance hierarchy. At the root of the hierarchy is the abstract class Expression. The class definition for Expression is contained in the file expression.h, shown below:
This abstract class has two subclasses. The first of these is SubExpression, which defines the node of the binary arithmetic expression tree. The class definition for SubExpression is contained in the file subexpression.h, shown below:
As is customary in C++, the bodies of the member functions of that class are contained in the file subexpression.cpp, shown below:
The SubExpression class has four subclasses. We show one of them—Plus. The class definition for Plus is contained in the file plus.h, shown below:
Because the bodies of both member functions are inline, no corresponding .cpp file is required.
The other subclass of Expression is Operand, which defines the leaf nodes of the arithmetic expression tree. The class definition for Operand is contained in the file operand.h, shown below:
The body of its only member function is contained in operand.cpp, shown below:
The Operand class has two subclasses. The first is Variable, which defines leaf nodes of the tree that contain variables. The class definition for Variable is contained in the file variable.h, shown below:
The body of its member function evaluate is contained in variable.cpp, shown below:
The other subclass of Operand is Literal, which defines leaf nodes of the tree that contain literal values. The class definition for Literal is contained in the file literal.h, shown below:
This interpreter uses a symbol table that is implemented with an unsorted list defined by the class SymbolTable. Its class definition is contained in the file symboltable.h, shown below:
The bodies of its member functions are in the file symboltable.cpp, shown below:
Finally, one utility function, parseName, is needed by this program. Its function prototype is the file parse.h, shown below:
Its body is in parse.cpp, shown below:
Explanation / Answer
#include "stdafx.h"
#include "parse.h"
int GetNumberTokens(char *s)
{
int numTokens = 0;
char *c, *temp;
int levelParen = 0;
bool empty = true;
bool inSimpleToken = false;
bool inParenToken = false;
for(c = s; (*c != '') && empty; c++)
if(!isspace(*c))
empty = false;
if(empty)
return -1;
if(!(c = strchr(s, '(')))
return 0;
c++;
temp = c;
for(; (*c != '') && (*c != ')') && empty; c++)
if(!isspace(*c))
empty = false;
if(empty)
return 0;
c = temp;
levelParen = 1;
for(; (*c != '') && (levelParen > 0); c++)
{
if(*c == ')')
{
levelParen--;
if(levelParen == 1)
inParenToken = false;
}
else if(*c == '(')
{
if(inSimpleToken)
inSimpleToken = false;
levelParen++;
if(levelParen == 2)
{
inParenToken = true;
numTokens++;
}
}
else if((!isspace(*c)) && (!inSimpleToken) && (!inParenToken))
{
inSimpleToken = true;
numTokens++;
}
else if(isspace(*c) && inSimpleToken)
{
inSimpleToken = false;
}
}
if(levelParen != 0)
return -2;
else
return numTokens;
}
bool GetToken(char *s, int n, char *dest)
{
char *c, *begin, *end;
int levelParen = 0;
int i;
int numTokens = 0;
bool inSimpleToken = false;
bool inParenToken = false;
bool done = false;
if(n == 0)
{
for(c = s; (*c != '') && (!done); c++)
{
if((!isspace(*c)) && (!inSimpleToken))
{
inSimpleToken = true;
begin = c;
}
else if(isspace(*c) && inSimpleToken)
{
done = true;
end = c - 1;
}
if(*(c + 1) == '' && inSimpleToken)
{
done = true;
end = c;
}
}
}
else
{
if(!(c = strchr(s, '(')))
return false;
c++;
levelParen = 1;
for(; (*c != '') && (levelParen > 0) && (!done); c++)
{
if(*c == ')')
{
levelParen--;
if(levelParen == 1)
{
inParenToken = false;
if(numTokens == n)
{
end = c;
done = true;
}
}
if(inSimpleToken)
{
inSimpleToken = false;
if(numTokens == n)
{
end = c - 1;
done = true;
}
}
}
else if(*c == '(')
{
if(inSimpleToken)
{
inSimpleToken = false;
if(numTokens == n)
{
end = c - 1;
done = true;
}
}
levelParen++;
if(levelParen == 2)
{
inParenToken = true;
numTokens++;
if(numTokens == n)
begin = c;
}
}
else if((!isspace(*c)) && (!inSimpleToken) && (!inParenToken))
{
inSimpleToken = true;
numTokens++;
if(numTokens == n)
begin = c;
}
else if(isspace(*c) && inSimpleToken)
{
inSimpleToken = false;
if(numTokens == n)
{
end = c - 1;
done = true;
}
}
}
}
if(!done)
return false;
for(c = begin, i = 0; (*c != '') && (c <= end); c++, i++)
dest[i] = *c;
dest[i] = '';
return true;
}
BuiltInOperator GetOperatorFromString(char *s)
{
if(s[0] == '+') return ADD;
else if(s[0] == '-') return SUB;
else if(s[0] == '*') return MULT;
else if(s[0] == '/') return DIV;
else if(s[0] == '^') return POWER;
else if((s[0] == 's') && (s[1] == 'i') && (s[2] == 'n')) return SIN;
else if((s[0] == 'c') && (s[1] == 'o') && (s[2] == 's')) return COS;
else if((s[0] == 't') && (s[1] == 'a') && (s[2] == 'n')) return TAN;
else if((s[0] == 'h') && (s[1] == 's') && (s[2] == 'i') && (s[3] == 'n')) return HSIN;
else if((s[0] == 'h') && (s[1] == 'c') && (s[2] == 'o') && (s[3] == 's')) return HCOS;
else if((s[0] == 'h') && (s[1] == 't') && (s[2] == 'a') && (s[3] == 'n')) return HTAN;
else if((s[0] == 'l') && (s[1] == 'o') && (s[2] == 'g')) return LOG;
else if(s[0] == '%') return MOD;
else return NONE;
}
void GetStringFromOperator(BuiltInOperator op, char *s)
{
switch(op)
{
case ADD:
s[0] = '+';
s[1] = '';
break;
case SUB:
s[0] = '-';
s[1] = '';
break;
case MULT:
s[0] = '*';
s[1] = '';
break;
case DIV:
s[0] = '/';
s[1] = '';
break;
case POWER:
s[0] = '^';
s[1] = '';
break;
case SIN:
s[0] = 's';
s[1] = 'i';
s[2] = 'n';
s[3] = '';
break;
case COS:
s[0] = 'c';
s[1] = 'o';
s[2] = 's';
s[3] = '';
break;
case TAN:
s[0] = 't';
s[1] = 'a';
s[2] = 'n';
s[3] = '';
break;
case HSIN:
s[0] = 'h';
s[1] = 's';
s[2] = 'i';
s[3] = 'n';
s[4] = '';
break;
case HCOS:
s[0] = 'h';
s[1] = 'c';
s[2] = 'o';
s[3] = 's';
s[4] = '';
break;
case HTAN:
s[0] = 'h';
s[1] = 't';
s[2] = 'a';
s[3] = 'n';
s[4] = '';
break;
case LOG:
s[0] = 'l';
s[1] = 'o';
s[2] = 'g';
s[3] = '';
break;
case MOD:
s[0] = '%';
s[1] = '';
break;
default:
s[0] = '';
break;
}
}
int GetNumberOperatorArgs(BuiltInOperator op)
{
if((op == ADD) || (op == SUB) || (op == MULT) || (op == DIV) ||
(op == POWER) || (op == MOD) || (op == LOG))
return 2;
else if((op == SIN) || (op == COS) || (op == TAN) ||
(op == HSIN) || (op == HCOS) || (op == HTAN) || (op == NONE))
return 1;
else
return -1;
}
bool ExtractSimpleOperandFromString(char *s, Operand *op)
{
double f;
Name token;
char *p;
if(GetToken(s, 0, token))
{
f = strtod(token, &p);
if(p[0] == '')
{
op->type = CONSTANT;
op->operand.value = f;
}
else
{
op->type = VAR;
strcpy(op->operand.var, token);
}
return true;
}
else
return false;
}
bool ExtractExpressionFromString(char *s, Expression *exp)
{
int numTokens;
char token[MAX_EXPRESSION_LENGTH];
int numArgs;
int i;
bool status = true;
numTokens = GetNumberTokens(s);
switch(numTokens)
{
case -2:
return false;
break;
case -1
return false;
break;
case 0:
exp->op = NONE;
exp->numArgs = 1;
exp->operand[0] = new Operand;
return ExtractSimpleOperandFromString(s, exp->operand[0]);
break;
case 1:
exp->op = NONE;
exp->numArgs = 1;
exp->operand[0] = new Operand;
exp->operand[0]->type = EXP;
exp->operand[0]->operand.exp = new Expression;
return(GetToken(s, 1, token) && ExtractExpressionFromString(token, exp));
break;
default:
if(!GetToken(s, 1, token))
return false;
exp->op = GetOperatorFromString(token);
if(exp->op == NONE)
return false;
numArgs = GetNumberOperatorArgs(exp->op);
if(numArgs != (numTokens - 1))
return false;
exp->numArgs = 0;
for(i = 1; (i <= numArgs) && status; i++)
{
if(!GetToken(s, (i + 1), token))
status = false;
else
switch(GetNumberTokens(token))
{
case -2:
status = false;
break;
case -1:
status = false;
break;
case 0:
exp->operand[i - 1] = new Operand;
status = ExtractSimpleOperandFromString(token, exp->operand[i - 1]);
break;
default:
exp->operand[i - 1] = new Operand;
exp->operand[i - 1]->type = EXP;
exp->operand[i - 1]->operand.exp = new Expression;
status = ExtractExpressionFromString(token, exp->operand[i - 1]->operand.exp);
break;
}
if(status)
exp->numArgs = exp->numArgs + 1;
}
return status;
break;
}
}
void PrintSimpleOperand(Operand *op, ofstream out)
{
switch(op->type)
{
case CONSTANT:
out << op->operand.value;
break;
case VAR:
out << op->operand.var;
break;
default:
break;
}
}
void PrintExpression(Expression *exp, ofstream out)
{
int i;
Name s;
switch(exp->op)
{
case NONE:
for(i = 0; i < exp->numArgs; i++)
{
switch(exp->operand[i]->type)
{
case EXP:
PrintExpression(exp->operand[i]->operand.exp, out);
break;
default:
PrintSimpleOperand(exp->operand[i], out);
break;
}
}
break;
default:
GetStringFromOperator(exp->op, s);
out << "(";
out << s;
for(i = 0; i < exp->numArgs; i++)
{
out << " ";
switch(exp->operand[i]->type)
{
case EXP:
PrintExpression(exp->operand[i]->operand.exp, out);
break;
default:
PrintSimpleOperand(exp->operand[i], out);
break;
}
}
out << ")";
break;
}
}