For this lab, write a C++ program that will evaluate an infix expression. The algorithm REQUIRED for this program will use two stacks, an operator stack and a value stack. Both stacks MUST be implemented using a dynamic array class (not struct) that you write.

The commands used by this system are listed below and are to come from standard input. Your program is to prompt the user for input and display error messages for unknown commands. The code in proj5Base.cpp already does this for you. You are expected to use that code as the base for your project.

Command	Description
q	Quit the program.
?	List the commands used by this program and a brief description of how to use each one.
	Evaluate the given infix expression and display its result.

The will only use the operators of addition, subtraction, multiplication, division and the parentheses. It will also only contain unsigned (i.e. positive) integer values. We obviously could allow for more operators and more types of values, but the purpose of this assignment is to focus on writing classes and not on complicated arithmetic expressions.

Infix Expression are when the operators of addition, subtraction, multiplication and division are listed IN between the values. Infix Expressions require the use of parentheses to express nonstandard precedence. Examples of Infix Expressions are:

42 + 64

60 + 43 * 18 + 57

(60 + 43) * (18 + 57)

18 12 3

18 (12 3)

Postfix Expressions are when the operators of addition, subtraction, multiplication and division are list AFTER (i.e. post) the values. Postfix Expression never require the use of parentheses to express non-standard precedence. The fact that postfix expressions do not need parentheses makes them much easier to evaluate than infix expressions. In fact, most computers first convert infix expression to a postfix expression and then evaluate that postfix expression.

A postfix expression is evaluated using a stack. When a value is encountered, it is pushed onto the stack. When an operator is encountered, two values are popped from the stack. Those values are evaluated using the operation implied by the operator. Then the result is pushed back onto the stack. When the end of a postfix expression is encountered, the value on the top of the stack is the result of the expression. There should only be one value on the stack when the end of the postfix expression is encountered.

Examples of Postfix Expressions are:

42 64 +

60 43 18 * + 57 +

60 43 + 18 57 + *

18 12 3 18 12 3

Both the algorithm to convert an infix expression to a postfix expression and the algorithm to evaluate a postfix expression require the use of stacks. Note that the conversion algorithm requires a stack of operators, while the evaluation algorithm requires a stack of values.

For this program, you are to write the following methods for the dynamic array stack class:

void init( ); // initialize the stack for use THIS MAY BE A CONSTRUCTOR boolean isEmpty ( ); // return true if the stack has no members

void push (data); // add the data to the top of stack; grow dynamic array if needed data top ( ); // return the data value on the top of the stack void pop ( ); // remove the data value from the top of the stack void reset ( ); // clear the stack to remove any values it contains

For this program, your dynamic array MUST start with 2 positions in the array. When the array needs to grow, it size MUST grow by 2 additional positions each time (note the array to grow in size from 2 to 4 to 6 to 8 to 10 to ...). Note the init( ) method to set up the stack should really be a constructor (but could be a normal method). You can also write a topPop( ) method that combine both the top and pop operations in a single method. Also, note that since the values from the infix expressions will all be integer values (we will only do integer division), and since the operators can all be represented as characters (which is a sub-class of integers), you are more than welcome to write a single stack class which store integers to be used for both stacks.

The instance/variable containing for each stack MUST be declared as a local variable to some method (it may be as a local variable to a method other than main( ) ). It may NOT be global. Each operation performed on the stack MUST be done in its own method. ALL data members of the stack class MUST use access modifier of private.

Algorithm for Infix to Postfix Conversation and Postfix Evaluation

First we will define the algorithm use for popAndEval ( ). This algorithm plays a critical role in the overall Evaluation of our expressions.

op = top (OperatorStack) pop (OperatorStack)

v2 = top (ValueStack) pop (ValueStack)

v1 = top (ValueStack) pop (ValueStack) v3 = eval ( v1, op, v2 ) push (ValueStack, v3)

To keep some of the error handling/recovery simple for this project, if you are trying to perform a top operation on an empty ValueStack, print out an error message and return the value of -999. If the operator op for eval ( ) is not one of *, /, + or -, print out and error message and return the value of -999. When getting the input for an infix expression, the program proj5Base.cpp breaks everything down into tokens. There are 3 types of tokens we are mostly concerned with: an OPERATOR token, a VALUE token and the EndOfLine token. The code in the function processExpression() already checks for these token but you will need to add the code how to interact with the stacks.

Provided Code for the User Inteface

The code given in proj5Base.cpp should properly provide for the user interface for this program including all command error checking. This program has no code for the stacks. It is your job to write the methods for the specified operations and make the appropriate calls. Most of the changes to the existing program need to be made in the processExpression ( ) method. Look for the comments of:

// add code to perform this operation here

Note: the instances containing the operator stack and value stack are required to be a local variable in a function. The function processExpression() is strongly suggested as the function in which to declared the instances of these stacks.

Use of Existing C++ Libraries

You are responsible to write the code for the dynamic array stacks yourself! This is the primary purpose of this project. Since the C++ Standard Template Libraries already contain a class called Stack, you should name your class something like MyStack to avoid confusion.

You are not allowed to use any of the classes from the C++ Standard Template Libraries in this program. These classes include ArrayList, Vector, LinkedList, List, Set, Stack, HashMap, etc. If you need such a class, you are to write it yourself.

--------------------------------Tokens.h file------------------------ #include #include #include

// Enumarated Type specifying all of the Tokens enum TokenType{ ERROR, OPERATOR, VALUE, EOLN, QUIT, HELP, EOFILE };

// Class to hold the Token information class Token { private: TokenType type; char op; // using '$' as undefined/error int val; // using -999 as undefined/error

public:

// Default to initialize to the ERROR TokenType Token();

// Initialize to a specific TokenType Token (TokenType t);

// Set to a specific TokenType void setToType(TokenType t);

// Set to a OPERATOR TokenType with specific operator value void setToOperator(char c);

// Set to a VALUE TokenType with a specific numeric value void setToValue(int v);

// return true if the Current Token is of the given TokenType bool equalsType(TokenType t);

// return true if the Current Token is of the OPERATOR TokenType // and contains the given operator character bool equalsOperator(char c);

// Return the Operator for the current Token // verify the current Token is of the OPERATOR TokenType char getOperator ();

// Return the Value for the current Token // verify the current token is of the value TokenType int getValue(); };

class TokenReader { private: char inputline[300]; // this assumes that all input lines are 300 characters or less in length bool needline; int pos;

public:

// initialize the TokenReader class to read from Standard Input TokenReader();

// Force the next getNextToken to read in a line of input void clearToEoln();

// Return the next Token from the input line Token getNextToken(); };

---------------------------------------------Token.cpp file-------------------------------------------------

#include "Tokens.h"

Token::Token() { type = ERROR; op = '$'; val = -999; }

// Initialize to a specific TokenType Token::Token (TokenType t) { type = t; op = '$'; val = -999; }

// Set to a specific TokenType void Token::setToType(TokenType t) { type = t; op = '$'; val = -999; }

// Set to a OPERATOR TokenType with specific operator value void Token::setToOperator(char c) { type = OPERATOR; op = c; val = -999; }

// Set to a VALUE TokenType with a specific numeric value void Token::setToValue(int v) { type = VALUE; op = '$'; val = v; }

// return true if the Current Token is of the given TokenType bool Token::equalsType(TokenType t) { if (type == t) return true; else return false; }

// return true if the Current Token is of the OPERATOR TokenType // and contains the given operator character bool Token::equalsOperator(char c) { if (type == OPERATOR && op == c) return true; else return false; }

// Return the Operator for the current Token // verify the current Token is of the OPERATOR TokenType char Token::getOperator () { if (type == OPERATOR) return op; else return '$'; // using $ to indicate an error value }

// Return the Value for the current Token // verify the current token is of the value TokenType int Token::getValue() { if (type == VALUE) return val; else return -999; // using -999 to indicate an error value }

// initialize the TokenReader class to read from Standard Input TokenReader::TokenReader() { // set to read from Standard Input inputline[0] = '\0'; pos = 0; needline = true; }

// Force the next getNextToken to read in a line of input void TokenReader::clearToEoln() { needline = true; }

// Return the next Token from the input line Token TokenReader::getNextToken() { char* endCheck;

//printf ("getToken %d, %d, %s ", pos, needline, inputline);

// get a new line of input from user if (needline) { endCheck = fgets ( inputline, 300, stdin);

if (endCheck == NULL ) { printf ("Error in reading"); Token t(EOFILE); return t; }

for (int i = 0 ; i

// skip over any white space characters in the beginning of the input while ( pos

// check for the end of the current line of input if (pos >= strlen(inputline)) { // at end of line needline = true; Token t(EOLN); return t; }

// Get the next character from the input line char ch = inputline[pos]; pos++;

// check if 'q' or 'Q' was entered ==> QUIT Token if ( 'q' == ch || 'Q' == ch ) { return Token (QUIT); }

// check if "?" was entered ==> HELP Token if ( '?' == ch ) { return Token (HELP); }

// check for Operator values of: + - * / ( ) ==> OPERATOR Token if ( ('+' == ch) || ('-' == ch) || ('*' == ch) || ('/' == ch) || ('(' == ch) || (')' == ch) ) { Token t; t.setToOperator( ch ); return t; }

// check for a number ==> VALUE Token if (isdigit(ch)) { int number = int (ch) - int('0'); // subtract ascii value of ch from ascii value of '0' ch = inputline[pos]; pos++; while (isdigit(ch)) { number = number * 10 + int (ch) - int('0'); ch = inputline[pos]; pos++; } pos--; // since number calcuation check one character after the last digit Token t; t.setToValue( number ); return t; }

// Input in not valid if code get to this part ==> ERROR Token return Token (ERROR); }

-----------------------------------------------------------Main.cpp file--------------------------------

#include "Tokens.h"

void printCommands();

void processExpression (Token inputToken, TokenReader *tr);

int main(int argc, char *argv[]) { /***************************************************************/ /* Add code for checking command line arguments for debug mode */

Token inputToken; TokenReader tr;

printf ("Starting Expression Evaluation Program "); printf ("Enter Expression: ");

inputToken = tr.getNextToken ();

while (inputToken.equalsType(QUIT) == false) { /* check first Token on Line of input */ if(inputToken.equalsType(HELP)) { printCommands(); tr.clearToEoln(); } else if(inputToken.equalsType(ERROR)) { printf ("Invalid Input - For a list of valid commands, type ? "); tr.clearToEoln(); } else if(inputToken.equalsType(EOLN)) { printf ("Blank Line - Do Nothing "); /* blank line - do nothing */ } else { processExpression(inputToken, &tr); }

printf (" Enter Expression: "); inputToken = tr.getNextToken (); }

printf ("Quitting Program "); return 1; }

void printCommands() { printf ("The commands for this program are: "); printf ("q - to quit the program "); printf ("? - to list the accepted commands "); printf ("or any infix mathematical expression using operators of (), *, /, +, - "); }

void processExpression (Token inputToken, TokenReader *tr) { /**********************************************/ /* Declare both stack head pointers here */

/* Loop until the expression reaches its End */ while (inputToken.equalsType(EOLN) == false) { /* The expression contain a VALUE */ if (inputToken.equalsType(VALUE)) { /* make this a debugMode statement */ printf ("Val: %d, ", inputToken.getValue() );

// add code to perform this operation here

}

/* The expression contains an OPERATOR */ else if (inputToken.equalsType(OPERATOR)) { /* make this a debugMode statement */ printf ("OP: %c, ", inputToken.getOperator() );

// add code to perform this operation here

}

/* get next token from input */ inputToken = tr->getNextToken (); }

/* The expression has reached its end */

// add code to perform this operation here

printf (" "); }

------------------------------------------------------makefile---------------------------------------

proj5: proj5Main.o proj5Tokens.o g++ -o proj5 proj5Main.o proj5Tokens.o

proj5Main.o: proj5Main.cpp proj5Tokens.h g++ -c proj5Main.cpp

proj5Tokens.o: proj5Tokens.cpp proj5Tokens.h g++ -c proj5Tokens.cpp

clean: rm proj5 proj5Main.o proj5Tokens.o

First step Empty both the OperatorStack and the ValueStack Second Step While (the current token is not the EndOfLine Token) if the current token is a VALUE) push the value onto the ValueStack if (the current operator is an Open Parenthesis) if ( the current operator is+or - if ( the current token is an OPERATOR) push the Open Parenthesis onto the OperatorStack while ( the OperatorStack is not Empty && the top of the OperatorStack is +, -, * or/) popAndEval ) push the current operator on the OperatorStack if ( the current operator is * or /) while ( the OperatorStack is not Empty && the top of the OperatorStack is * or/) popAndEval ) push the current operator on the OperatorStack while ( the Operator Stack is not Empty && if (the OperatorStack is Empty) else if ( the current operator is a Closing Parenthesis) the top of the OperatorStack is not an Open Parenthesis) popAndEval () print an error message pop the Open Parenthesis from the OperatorStack get the next token from the input First step Empty both the OperatorStack and the ValueStack Second Step While (the current token is not the EndOfLine Token) if the current token is a VALUE) push the value onto the ValueStack if (the current operator is an Open Parenthesis) if ( the current operator is+or - if ( the current token is an OPERATOR) push the Open Parenthesis onto the OperatorStack while ( the OperatorStack is not Empty && the top of the OperatorStack is +, -, * or/) popAndEval ) push the current operator on the OperatorStack if ( the current operator is * or /) while ( the OperatorStack is not Empty && the top of the OperatorStack is * or/) popAndEval ) push the current operator on the OperatorStack while ( the Operator Stack is not Empty && if (the OperatorStack is Empty) else if ( the current operator is a Closing Parenthesis) the top of the OperatorStack is not an Open Parenthesis) popAndEval () print an error message pop the Open Parenthesis from the OperatorStack get the next token from the input