C++

Recursive function:

a recursive implementation of a logic calculator using a stack container

#ifndef LOGICCALCULATOR_H #define LOGICCALCULATOR_H

#include #include #include #include #include

using namespace std;

/* * NOTE: DO NOT MODIFY THIS FILE. * It should not be submitted for Fitchfork evaluation and will be overwritten if it is. */

class LogicCalculator {

private: /* * A container that stores the characters of a logic expression. * The container should not contain any whitespace characters. The characters * are added each time a new expression is given. */ deque expression; /* * A container that contains characters of a logic expression in postfix notation */ deque postfix; /* * A container that contains unique variables (alphabets) obtained from a logic * expression. The characters are added in alphabetical order. */ list vars; /* * A collection of all operators supported by the calculator. It helps to add the * operators to this container in their order of precedence. */ vector operators; /* * A container that contains boolean values associated with the sorted unique variables * of an expression. The vars container and this values container have a one-to-one mapping. */ vector values; /* * A stack container that is used in the computation of a logic expression. The container * should be empty prior to any calculation. */ stack> calcStack; /* * A flag to indicate if the program is in debug mode or not. Its default value is false. */ bool debug; public: /* * The constructor should initialize relevant private variables and add the supported * operators to the operators container. */ LogicCalculator(); /* * Destructor */ ~LogicCalculator(); /* * The evaluate function should compute the logic value for the given expression. It * should accomplish this by tokenizing the input expression into single non-whitespace * characters, computing the postfix notation, prompting the user to enter Boolean values * for each unique variable in the expression (in alphabetical order), computing the answer * by invoking the 'compute' recursive function and thereafter returning the boolean answer. */ bool evaluate(string expression); /* * The overloaded evaluate function should accomplish the same task as described above. It should * however skip the step of prompting the user for boolean values and use the values in the vals * parameter instead. The boolean values in vals should correspond to the sorted unique variables * in the given expression (one-to-one mapping). The function should return the computed answer. */ bool evaluate(string expression, vector vals); /* * Sets the debug variable to the input boolean value. */ void setDebug(bool); /* * This function accepts a string expression as input and should return its postfix equivalent. * It accomplishes this by first tokenizing the input expression into single non-whitespace characters, * then computing the postfix expression by invoking the 'convert' helper function and thereafter * returning the solution as a string. */ string convertToPostfix(string expression); /* * Returns the postfix expression stored in the postfix container as a string (e.g. AB|=). There * should not be any whitespace between the characters in the returned string. */ string getPostfix() const; /* * Returns the infix expression stored in the expression container as a string (e.g. A|B=). There * should not be any whitespace between the characters in the returned string. */ string getExpression() const;

private: /* ================ Compulsory Helper Functions ================= */ /* * The reset function should reset all relevant containers involved in the processing and * computation of a logic expression. It should be called prior to any calculator computation. */ void reset(); /* * This helper function should convert the given input string into individual characters and store * them in the expression container. The conversion process should include removal of whitespace * characters and add an "equals to" symbol (=) should it not be present at the end of the string. */ void tokenizeExpression(string); /* * The convert function implements the shunting-yard algorithm to convert an infix expression stored * in the expression container to a postfix expression. It should follow the pseudocode given * in the assignment spec and throw runtime errors when it encounters unrecognized characters * (tokens) or mismatched parentheses. * * For example: throw std::runtime_error("error description"); * * Only two types of errors are expected and their format should be: * ERROR: unrecognized token {token} //where {token} stands for the currently processed char * ERROR: mismatched parentheses * * Based on: https://en.wikipedia.org/wiki/Shunting-yard_algorithm */ void convert(); /* * This function should obtain unique variables (letters) from the expression container and store * these unique variables in alphabetical order in the vars container. */ void computeUniqueVars(); /* * The compute function is a recursive function that is used to compute the boolean value of * a logic expression using a STACK as the computer. The expression is assumed to be already * converted into its postfix notation. The function should start with a copy of the postfix * expression and recursively process the expression according to Algorithm 2 in the spec * using the calcStack container as the calculator stack. It should make use of the boolean * variables in the vals container to substitute the corresponding variables before pushing them * onto the calcStack container for computation. * * When in debug mode, the function should print out statements corresponding to the read * character token and the stack operations used. Only the following debug statements should be * used: * Token is variable: {letter} (e.g. Token is variable: B) * Token is operator: {operator} (e.g. Token is operator: &) * PUSH {value} onto STACK (e.g. PUSH 1 onto STACK) * POP {value} from STACK (e.g. POP 0 from STACK) * * The function should throw a generic runtime error should it not be able to successfully * compute the solution of the expression. The error message should be: * ERROR: could not compute {expression} * where {expression} is replaced with the contents of the expression container */ bool compute(deque); /* * This helper function determines if operator op2 has a higher or the same * precedence as that of operator op1. The function should return true if: * precedence(op2) >= precedence(op1), and false otherwise * The precedence order from highest to lowest is: * NOT > NAND > NOR > AND > XOR > OR */ bool isPrecedenceGreaterEqual(char op1, char op2); /* ================ Optional Helper Functions ================= */ // The following helper functions are not necessary as you can implement this inline. // If you choose to not make use of them, simply return false in the function bodies in // your LogicCalculator.cpp file /* * Computes the NAND (inverted AND) operation and returns the boolean result */ bool nand(bool a, bool b); /* * Computes the NOR (inverted OR) operation and returns the boolean result */ bool nor(bool a, bool b);

};

#endif // LOGICCALCULATOR_H

output:

--------------------------------------- Testing Postfix Conversion --------------------------------------- AB|= AC!&= AB|C&= ABC&|=

-------------------------------------------- Testing Logic Calculator (debug=1) -------------------------------------------- Evaluate A|B:

Token is variable: A PUSH 0 onto STACK Token is variable: B PUSH 1 onto STACK Token is operator: | POP 1 from STACK POP 0 from STACK PUSH 1 onto STACK A|B=AB|=1

Evaluate B | (!(C ^ A)):

Token is variable: B PUSH 0 onto STACK Token is variable: C PUSH 1 onto STACK Token is variable: A PUSH 1 onto STACK Token is operator: ^ POP 1 from STACK POP 1 from STACK PUSH 0 onto STACK Token is operator: ! POP 0 from STACK PUSH 1 onto STACK Token is operator: | POP 1 from STACK POP 0 from STACK PUSH 1 onto STACK B|(!(C^A))=BCA^!|=1

-------------------------------------------- Testing Logic Calculator (debug=0) -------------------------------------------- A+B|(C+!D)=AB+CD!+|=0 Z+!C=ZC!+=1

--------------------------------------------------------- Testing Logic Calculator (prompt=1, debug=0) --------------------------------------------------------- Expression 1: Enter truth value for C: 1 Enter truth value for E: 1 C+E&C=CE+C&=0

Expression 2: Enter truth value for E: 1 Enter truth value for F: 0 F+!E=FE!+=1

--------------------------------------------------------- Testing Logic Calculator (error handling) --------------------------------------------------------- ERROR: mismatched parentheses ERROR: unrecognized token - ERROR: could not compute A|=

MAIN:

#include #include #include "LogicCalculator.h" #include

using namespace std;

int main() {

LogicCalculator calc; /*--- Test Postfix Conversion -----*/ cout << "--------------------------------------- "; cout << " Testing Postfix Conversion "; cout << "--------------------------------------- "; cout << calc.convertToPostfix("A|B") << endl; cout << calc.convertToPostfix("A&!C=") << endl; cout << calc.convertToPostfix("(A | B) & C=") << endl; cout << calc.convertToPostfix("A | (B&C)") << endl; /*--- Test Logic Calculator in debug mode -----*/ cout << " -------------------------------------------- "; cout << " Testing Logic Calculator (debug=1) "; cout << "-------------------------------------------- "; bool answer; string expr; calc.setDebug(true); vector v1 = {0,1}; //A=0, B=1 expr = "A|B"; cout << "Evaluate " << expr << ": "; answer = calc.evaluate(expr, v1); cout << calc.getExpression() << calc.getPostfix() << answer << endl; vector v2 = {1,0,1}; //A=1, B=0, C=1 expr = "B | (!(C ^ A))"; cout << " Evaluate " << expr << ": "; answer = calc.evaluate(expr, v2); cout << calc.getExpression() << calc.getPostfix() << answer << endl; calc.setDebug(false); /*--- Test Logic Calculator in normal mode -----*/ cout << " -------------------------------------------- "; cout << " Testing Logic Calculator (debug=0) "; cout << "-------------------------------------------- "; vector v3 = {0,1,1,0}; //A=0, B=1, C=1, D=0 answer = calc.evaluate("A+B | (C + !D)", v3); cout << calc.getExpression() << calc.getPostfix() << answer << endl; vector v4 = {1,0}; //C=1, Z=0 answer = calc.evaluate("Z + !C", v4); cout << calc.getExpression() << calc.getPostfix() << answer << endl;

/*--- Test Logic Calculator user prompts -----*/ cout << " --------------------------------------------------------- "; cout << " Testing Logic Calculator (prompt=1, debug=0) "; cout << "--------------------------------------------------------- "; cout << "Expression 1: "; answer = calc.evaluate("C + E & C"); cout << calc.getExpression() << calc.getPostfix() << answer << endl; cout << " Expression 2: "; answer = calc.evaluate("F + !E"); cout << calc.getExpression() << calc.getPostfix() << answer << endl; /*--- Test Logic Calculator error handling -----*/ cout << " --------------------------------------------------------- "; cout << " Testing Logic Calculator (error handling) "; cout << "--------------------------------------------------------- "; try { cout << calc.convertToPostfix("A|B)") << endl; } catch (const std::exception& ex) { cerr << ex.what() << endl; } try { cout << calc.convertToPostfix("A-B)") << endl; } catch (const std::exception& ex) { cerr << ex.what() << endl; } try { calc.evaluate("A|=", v1); //A=0, B=1 } catch (const std::exception& ex) { cerr << ex.what() << endl; } return 0; }