Using the C$++$ code at the bottom, complete the expression evaluator based on the recursive descent parser.

$****$Sample Output$***$

"Welcome to the expression calculator.

Please use $+,-,*,/,(,)$ and nonnegative integers only.

Type the next expression or Enter to quit: $45$

$45=45$

Type the next expression or Enter to quit: $45+5*6$

$45+5*6=75$

Type the next expression or Enter to quit: $99*(2+11)-(5-1)$

$99*(2+11)-(5-1)=1283$

Type the next expression or Enter to quit:"

$*****$END SAMPLE OUTPUT$***$

$***$Guidelines for assignment$***$

Not just parsing the expression, we are evaluating it$.$

If the return value is true and the expression is valid then the value will be stored in the reference paramete value. For simplicity we will forgo variables and just use nonnegative integer constants as our operands. To get the value a nonnegative integer, represented as a string, please use the multiply and add method. $($Multiply the running total by $10$ then add the numeric value of the next digit.$)$ Stop when you get to a nondigit and return true. If the very first character is not a digit $($the character at currentIndex$)$ then return false.

Use only basic operations in your function implementations. No calls to any library functions whatsoever.

No use of any data types besides int, char, bool, along with array of char.

You must use C$++$ and make no modifications to main.

$****$HERE IS THE PROVIDED TEMPLATE$***$

#include

using namespace std;

bool expression$($char tokens$[],$ int numTokens, int& currentIndex, int& value$)$;

bool intConstant$($char tokens$[],$ int numTokens, int& currentIndex, int& value$)$;

bool factor$($char tokens$[],$ int numTokens, int& currentIndex, int& value$)$;

bool term$($char tokens$[],$ int numTokens, int& currentIndex, int& value$)$;

int main$()$

$\{$

char line$[80]="",$ tokens$[80]=""$;

cout $<<$ "Welcome to the expression calculator. $"<<$ endl;

cout $<<$ "Please use $+,-,*,/,(,)$ and nonnegative integers only." $<<$ endl $<<$ endl;

int numToks $=0$;

do $\{$

cout $<<$ "Type the next expression or Enter to quit: $"$;

cin.getline$($line$,80)$;

numToks $=0$;

for $($int i $=0$; line$[$i$]!=\text{'}\backslash 0\text{'}$; i$++)$

if $($line$[$i$]!=\text{'}\text{'})$

tokens$[$numToks$++]=$ line$[$i$]$; $//$ omit spaces

tokens$[$numToks$]=\text{'}\backslash 0\text{'}$;

if $($numToks $>0)\{$

int currentIndex $=0,$ value; $//$ value will store the result

bool valid $=$ expression$($tokens$,$ numToks, currentIndex, value$)$;

if $($valid$)$

cout $<<$ tokens $<<"="<<$ value;

else

cout $<<$ "Not a valid expression.";

cout $<<$ endl $<<$ endl;

$\}$

$\}$ while $($numToks $>0)$;

return $0$;

$\}$

bool intConstant$($char tokens$[],$ int numTokens, int& currentIndex, int& value$)\{$

$//$ Declare a variable to store the current token and initialize it to tokens$[$currentIndex$].$

$//$ Check that the token represents a digit. If not, then just return false.

$//$ Initialize parameter value to zero.

while $(/*$ the current token represents a digit $*/)\{$

$//$ multiply value by $10,$ then add the current token$$s digit value.

$//$ Increment currentIndex and get the next token.

$\}$

return true;

$\}$

bool factor$($char tokens$[],$ int numTokens, int& currentIndex, int& value$)\{$

$//$ If the current token is $\text{'}(\text{'}$ then do the following:

$//$ Increment currentIndex to consume the $\text{'}(\text{'}$

$//$ Call expression$()$ to check for an expression and update value.

$//$ If expression returns false, then return false.

$//$ Otherwise, check that there are still more tokens. $($If not, return false.$)$

$//$ Check that the next token is $\text{'})\text{'}($If not, return false.$)$

$//$ Increment currentIndex to consume the $\text{'})\text{'}$ and return true.

$//$ If the current token is NOT $\text{'}(\text{'}$ then assume it's an integer constant and

$//$ return whatever intConstant$()$ returns.

$\}$

bool term$($char tokens$[],$ int numTokens, int& currentIndex, int& value$)\{$

$//$ Call factor$()$ to process the first factor.

$//$ If factor$()$ returns false, then return false.

$//$ If there are no more tokens then return true.

$//$ Otherwise do the following in a loop:

$//$ If the next token is $\text{'}*\text{'}$ or $\text{'}/\text{'}$ then $...$

$//$ Consume the token.

$//$ Declare a local variable v and call factor$()$ with v as the last argument

$//$ If factor$()$ returns false then return false.

$//$ Otherwise multiply or divide value by v$,$ as appropriate.

$//$ If the next token is not $\text{'}*\text{'}$ or $\text{'}/\text{'}$ then exit the loop and return true.

$\}$

bool expression$($char tokens$[],$ int numTokens, int& currentIndex, int& value$)\{$

$//$ Call term$()$ to process the first term.

$//$ If term$()$ returns false, then return false.

$//$ If there are no more tokens then return true.

$//$ Otherwise do the following in a loop:

$//$ If the next token is $\text{'}+\text{'}$ or $\text{'}-\text{'}$ then $...$

$//$ Consume the token.

$//$ Declare a local variable v and call term$()$ with v as the last argument

$//$ If term$()$ returns false then return false.

$//$ Otherwise add v to value or subtract v from value, as appropriate.

$//$ If the next token is not $\text{'}+\text{'}$ or $\text{'}-\text{'}$ then exit the loop.

$//$ Return true if all the tokens were consumed and return false, otherwise.

$\}$