Create a C++ program that supposed to be a calculator for the algebraic expression

3 + 2 * 6 (1 + 5 * 8 + 4) + 5; without the use of grammar.

Use the following steps:

1. Use the get_Token() function to read input and place tokens into a vector. Make sure that left and right parentheses ( and ) are also tokens.

2. By traversing the vector first to last, find the position i of the rightmost (By traversing the vector last to first, find the position j of the leftmost). If there are no parentheses, then i= 0 and j=v.size()-1.

3. If there are parentheses, evaluate the subexpression inside them, that is from v [i+1] to v[j-1]. If there are not, evaluate the expression from v[0] to v[v.size()-1]. For example, if the subexpression is x + a*b/c*d + e :

a. First evaluate the mul/div p= a*b/c*d.

b. Change the expression to x + p + 0 + 0 + 0 + e, by replacing b, c, d by 0 and all the 3 mul/div by +.

c. Repeat this if necessary, so that the subexpression contains only +s or s.

d. Now evaluate the subexpression. Store its value into a token s.

Replace v[i] by s.

e. Remove the tokens from position i+1 to position j.

4. Repeat steps 2 and 3 until the token vector has only one token, which is the value to be computed.

Fill in the code in the following program :

class Token {

public:

char kind; // what kind of token

double value; // for numbers: a value

Token() // make a trivial token

{

kind = 0;

value = 0;

}

Token(char ch) // make a Token from a char

{

kind = ch;

value = 0;

}

Token(char ch, double val) // make a Token from a char and a double

{

kind = ch;

value = val;

}

friend ostream& operator<< (ostream& out, const Token& tok ) // in order for "cout << token;" to work

{

if ( tok.kind == '8' )

out << tok.value;

else

out << tok.kind;

return out;

}

};

//------------------------------------------------------------------------------

// prints the tokens of the vector (it should look like an algebraic expression)

void print( const vector& v )

{

// fill in your code here

}

//------------------------------------------------------------------------------

Token get_token() // read a token from cin

{

Token tok;

char ch;

cin >> ch; // note that >> skips whitespace (space, newline, tab, etc.)

switch (ch) {

case '(': case ')': case '+': case '-': case '*': case '/': case ';': case 'q':

{

tok = Token(ch); // let each character represent itself

break;

}

case '.':

case '0': case '1': case '2': case '3': case '4':

case '5': case '6': case '7': case '8': case '9':

{

cin.putback(ch); // put digit back into the input stream

double val;

cin >> val; // read a floating-point number

tok = Token('8',val); // let '8' represent "a number"

break;

}

default:

error("Bad token");

}

return tok;

}

//------------------------------------------------------------------------------

// remove len tokens from vector starting with v[pos]

void remove_token( vector& v, size_t pos, size_t len ) {

// starting pos is too large

if ( pos >= v.size() )

return;

// starting pos is ok, remove from v[pos] on

if ( pos+len >= v.size() )

{

if ( pos == 0 )

v.clear(); // clear the whole vector

else

{

size_t j = v.size() - pos; // num of elem to remove

for (size_t i = 0; i < j; i++ )

v.pop_back();

}

return;

}

// the case when pos+len < v.size()

size_t i,j;

// copy the tail of the vector over starting with v[pos]

for (i = pos+len, j = pos; i < v.size(); i++, j++ )

v[j] = v[i];

// remove the last len entries

for (i = 0; i < len; i++ )

v.pop_back();

}

//------------------------------------------------------------------------------

// to evaluate a subexpression between v[beg] and v[end]

// not containing parantheses; tokens are removed in the process

double evaluate_subexpression( vector&v, size_t beg, size_t end )

{

if ( beg == end )

return v[beg].value;

double subval;

// write your code here

return subval;

}

//------------------------------------------------------------------------------

// to evaluate an expression possibly containing parantheses;

// it calls evaluate_subexpression;

// it is responsible for removing parantheses once the expression between () is computed

double evaluate( vector& v )

{

double val = 0.0;

size_t beg, end; // position of rightmost '(' and left most ')'

bool lparenfound, rparenfound;

if ( v.size() == 1 )

{

val = v[0].value;

v.clear();

return val;

}

// write your code here

while ( v.size() > 1 )

{

}

v.clear();

return val;

}

//------------------------------------------------------------------------------

int main()

{

try

{

vector v;

Token tok;

double val = 0;

cout << "Welcome to our calculartor! Enter an expression. "

<< "End with ';' to evaluate. "

<< "End with 'q' to quit. ";

while ( true )

{