Code:
#include <iostream>
#include <string>
using namespace std;
#include "CalcTree.h"
//this enumeration defines the token types
enum Token{LPAREN, RPAREN, PLUS, MINUS, MULT, DIVIDE, OPERAND, ETR, EXT, ERR};
//LPAREN - left parenthesis
//RPAREN - right parenthesis
//PLUS - plus symbol
//MINUS - minus symbol
//MULT - multiply symbol
//DIVIDE - divide symbol
//OPERAND - an integer operand
//ETR - the enter key
//EXT - the exit token
//ERR - the error token (parse error)
//this function parses the cin stream and returns the next single token found
Token parse( int& operand, string& message );
//if an operand token is found, it is placed in the reference parameter "operand"
//if an error is encountered, an error message will be placed in the reference parameter "message"
//this function builds an expression tree from the parsed input tokens
//returns true if a valid expression was built, false otherwise
bool BuildEXP( CalcTree& expression );
int main( )
{
cout<<"Welcome to the simple calculator."<<endl;
bool POSTFIX = false; //default to infix notation printing
char choice; //user choice
cout<<"Would you like to print expressons in POSTFIX before evaluating? (y/n)"<<endl;
cin.get(choice); //get user choice
cin.ignore(255,'\n');
//loop as long as user doesn't enter a valid choice
while(choice!='y' && choice!='Y' && choice!='n' && choice!='N')
{
cout<<"Invalid choice...would you like to activate POSTFIX mode? (y/n)"<<endl;
cin.get(choice); //get user choice
cin.ignore(255,'\n');
}
if(choice=='Y' || choice=='y') POSTFIX = true; //set boolean if user wants postfix printing
//give user instructions
cout<<"Enter any INFIX expression."<<endl;
cout<<"Use only operators + , - , * , and /"<<endl;
cout<<"Use only integer operands and parenthesize your expressions!"<<endl;
cout<<"Type \"EXIT\" to quit."<<endl<<endl;
int operand; //store a parsed operand
string message; //store an error message
Token next; //store the next token coming from the input
CalcTree expression; //store the parsed expression in a tree structure
next = parse(operand,message); //get the first token from the input
while( next != EXT ) //while the token is not the exit token
{
if(next==LPAREN) //if the token is left parenthesis
{
bool result = BuildEXP( expression ); //build an expression
if(!result) //if the expression doesn't build properly
{
cout<<endl<<"Syntax error: Invalid Expression!";
}
else //if it is built properly
{
//re-print the expression in the user's desired format
cout<<endl;
if(POSTFIX) expression.printPOST();
else expression.printIN();
cout<<" = "<<expression.evaluate(); //evaluate the expression
cin.ignore(255,'\n');
}
}
else if(next==ERR) //if the token is an error
{
cout<<endl<<message; //output the error message
}
else //if the token is anything else, the expression doesn't begin properly
{
cout<<endl<<"Syntax error: Expressions must begin with \"(\".";
}
cout<<endl<<endl; //move prompt past any output messages
next = parse(operand,message); //get the next token
}
}
Token parse( int& operand, string& message )
{
string history=""; //keep history of characters gotten for multi-character tokens
char next; //store the next character from the input
cin.get(next); //get the next character from the input
if(next=='(') return LPAREN; //left parenthesis found
else if(next==')') return RPAREN; //right parenthesis found
else if(next=='+') return PLUS; //plus sign found
else if(next=='-') return MINUS; //minus sign found
else if(next=='*') return MULT; //multiplication symbol found
else if(next=='/') return DIVIDE; //division symbol found
else if(next=='\n') return ETR; //new like character (enter) found
else if(next=='E' || next=='e') //check for exit token if an E or e is found
{
history=history+next; //store the E or e
cin.get(next); //get the next character
if(next=='X' || next=='x') //if an X or x is found continue looking for exit
{
history=history+next; //store the X or x
cin.get(next); //get the next character
if(next=='I' || next=='i') //if an I or i is found continue looking for exit
{
history=history+next; //store the I or i
cin.get(next); //get the next character
if(next=='T' || next=='t') //if a T or t is found, we have exit
{
return EXT;
}
else //if not T or t, it's a parse error
{
message = "Parse error: unrecognized input token \""+history+next+"\".";
return ERR;
}
}
else //if not I or i, it's a parse error
{
message = "Parse error: unrecognized input token \""+history+next+"\".";
return ERR;
}
}
else //if not X or x, it's a parse error
{
message = "Parse error: unrecognized input token \""+history+next+"\".";
return ERR;
}
}
else if(isdigit(next)) //check for an operand (begins with a digit)
{
history=history+next; //store the current digit character in the history
while(isdigit(cin.peek())) //peek at the next input character, is it another digit?
{
cin.get(next); //if so, get it and add it to the history
history=history+next;
}//at the end of this loop, all consecutive digits found are in the "history" string
operand = atoi(history.c_str()); //convert the digit characters to an actual number
return OPERAND;
}
else //unrecognized character
{
message = "Parse error: unrecognized input character \"";
message = message+next;
message = message+"\".";
return ERR;
}
}
bool BuildEXP( CalcTree& expression )
{
CalcTree left, right; //create trees for the left and right sub-expressions
int operand; //store an operand
string message; //store an error message
Token next; //store the next token
//get first part of expression
//should be an operand or another sub-expression
next = parse(operand,message);
if(next==LPAREN) //left parenthesis here means there is a left sub-expression
{
bool Lresult = BuildEXP( left ); //build the left expression tree
if(!Lresult) //if there is an error in the left expression
{
cin.ignore(255,'\n'); //clear all remaining input
return false; //return an error code
}
}
else if(next==OPERAND) //operand here means no left sub-expression
{
left.setRoot(OPR,operand); //just set the left tree to the operand value
}
// All of these are errors, the first part of an expression should not be any of these! //
else if(next==PLUS)
{
cout<<endl<<"Syntax error: Found operator \"+\" when operand or sub-expression expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==MINUS)
{
cout<<endl<<"Syntax error: Found operator \"-\" when operand or sub-expression expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==MULT)
{
cout<<endl<<"Syntax error: Found operator \"*\" when operand or sub-expression expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==DIVIDE)
{
cout<<endl<<"Syntax error: Found operator \"/\" when operand or sub-expression expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==ETR)
{
cout<<endl<<"Syntax error: End of line found in middle of expression";
return false;
}
else if(next==EXT)
{
cout<<endl<<"Syntax error: Exit token found in middle of expression";
cin.ignore(255,'\n');
return false;
}
else if(next==RPAREN)
{
cout<<endl<<"Syntax error: \")\" found before expected";
cin.ignore(255,'\n');
return false;
}
else if(next==ERR)
{
cout<<endl<<message;
cin.ignore(255,'\n');
return false;
}
//get second part of expression
//should be an operator
next = parse(operand,message);
//look for one of the four operators, if found place at the root of this expression tree
if(next==PLUS)
{
expression.setRoot(ADD,0);
}
else if(next==MINUS)
{
expression.setRoot(SUB,0);
}
else if(next==MULT)
{
expression.setRoot(MUT,0);
}
else if(next==DIVIDE)
{
expression.setRoot(DIV,0);
}
// All of these are errors, the second part of an expression should not be any of these! //
else if(next==LPAREN)
{
cout<<endl<<"Syntax error: Found sub-expression when operator was expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==OPERAND)
{
cout<<endl<<"Syntax error: Found operand when operator was expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==ETR)
{
cout<<endl<<"Syntax error: End of line found in middle of expression";
return false;
}
else if(next==EXT)
{
cout<<endl<<"Syntax error: Exit token found in middle of expression";
cin.ignore(255,'\n');
return false;
}
else if(next==RPAREN)
{
cout<<endl<<"Syntax error: \")\" found before expected";
cin.ignore(255,'\n');
return false;
}
else if(next==ERR)
{
cout<<endl<<message;
cin.ignore(255,'\n');
return false;
}
//get third part of expression
//should be an operand or another sub-expression
next = parse(operand,message);
if(next==LPAREN) //left parenthesis here means there is a right sub-expression
{
bool Rresult = BuildEXP( right ); //build the right expression tree
if(!Rresult) //if there is an error in the right expression
{
cin.ignore(255,'\n'); //clear all remaining input
return false; //return an error code
}
}
else if(next==OPERAND) //operand here means no right sub-expression
{
right.setRoot(OPR,operand); //just set the right tree to the operand value
}
// All of these are errors, the third part of an expression should not be any of these! //
else if(next==PLUS)
{
cout<<endl<<"Syntax error: Found operator \"+\" when operand or sub-expression expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==MINUS)
{
cout<<endl<<"Syntax error: Found operator \"-\" when operand or sub-expression expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==MULT)
{
cout<<endl<<"Syntax error: Found operator \"*\" when operand or sub-expression expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==DIVIDE)
{
cout<<endl<<"Syntax error: Found operator \"/\" when operand or sub-expression expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==ETR)
{
cout<<endl<<"Syntax error: End of line found in middle of expression";
return false;
}
else if(next==EXT)
{
cout<<endl<<"Syntax error: Exit token found in middle of expression";
cin.ignore(255,'\n');
return false;
}
else if(next==RPAREN)
{
cout<<endl<<"Syntax error: \")\" found before expected";
cin.ignore(255,'\n');
return false;
}
else if(next==ERR)
{
cout<<endl<<message;
cin.ignore(255,'\n');
return false;
}
//get fourth part of expression
//should be a right parenthesis
next = parse(operand,message);
if(next==RPAREN) //right parenthesis means the end of an expression
{
expression.setLeft(left); //set the left subtree of this expression to the left expression tree
expression.setRight(right); //set the right subtree of this expression to the right expression tree
}
// All of these are errors, the third part of an expression should not be any of these! //
else if(next==LPAREN)
{
cout<<endl<<"Syntax error: Found sub-expression when \")\" was expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==PLUS)
{
cout<<endl<<"Syntax error: Found operator \"+\" when \")\" expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==MINUS)
{
cout<<endl<<"Syntax error: Found operator \"-\" when \")\" expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==MULT)
{
cout<<endl<<"Syntax error: Found operator \"*\" when \")\" expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==DIVIDE)
{
cout<<endl<<"Syntax error: Found operator \"/\" when \")\" expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==OPERAND)
{
cout<<endl<<"Syntax error: Found operand when \")\" was expected.";
cin.ignore(255,'\n');
return false;
}
else if(next==ETR)
{
cout<<endl<<"Syntax error: End of line found in middle of expression";
return false;
}
else if(next==EXT)
{
cout<<endl<<"Syntax error: Exit token found in middle of expression";
cin.ignore(255,'\n');
return false;
}
else if(next==ERR)
{
cout<<endl<<message;
cin.ignore(255,'\n');
return false;
}
return true; //return success (no erros have been encountered
}
confusing eh. it's tokenizing then parsing the functions which we honestly havent been over alot in class.
