Problem CALCULATOR

Input: A fully parenthesized expression E, where each operand is a single digit in {0, 1, , 9}, and three operators are + (binary addition) , * (binary multiplication), and ^ (binary power). You can assume that input is correct and fully parenthesized

Output: Equivalent postfix expression to E, and the result of evaluating E in modulo 10.

Write a C++ program for Problem CALCULATOR. Pay attention to the following:

Include the following STACK implementation in your program:

class STACK

{

private:

char *s; int N;

public:

STACK(int maxN)

{ s = new char[maxN]; N = 0; }

int empty() const

{ return N == 0; }

void push(char item)

{ s[N++] = item; }

char pop()

{ return s[--N]; }

};

You may find the following program segment useful. It converts a given fully parenthesized infix expression in a[] to an equivalent postfix expression (for +, and *).

int main()

{ char a[]; //read from the input

int N = strlen(a);

STACK ops(N);

for (int i = 0; i < N; i++)

{

if (a[i] == ')')

cout << ops.pop() << " ";

if ((a[i] == '+') || (a[i] == '*'))

ops.push(a[i]);

if ((a[i] >= '0') && (a[i] <= '9'))

cout << a[i] << " ";

} cout << endl;

}

You may find the following program segment useful (please note that it does not include unary ^ therefore you need to add it). It is designed to evaluate the given postfix expression in a[]. It does that in modulo 10. Therefore, all results (including intermediate results) are single decimal digits in {0, 1, , 9}. Therefore, you store only single digits in the stack. This program segment may be incomplete and you may need to make simple modifications to correct. For example, you need to convert characters to integers to do arithmetic on them. Also note that the stack name is save (not ops) in this case.

int main(

{ char a[]; // a[] should be the postfix expression obtained from original expression

int N = strlen(a);

STACK save(N);

for (int i = 0; i < N; i++)

{

if (a[i] == '+')

save.push((save.pop() + save.pop()) % 10);

if (a[i] == '*')

save.push((save.pop() * save.pop()) % 10 );

if ((a[i] >= '0') && (a[i] <= '9'))

save.push(a[i]);

}

cout << save.pop() << endl;

} ;

Correctness and efficiency are both important for your program.

Example Dialogue (input can be read from a specific file, or can be directed to a file):

Expression?: (((2+(5^2))+7)

Answer:

252^+7+

4 in modulo 10

Expression?: ((((2+5)*7)+((9*3)*2))^2)

Answer:

25+7*93*2*+2^

9 in modulo 10

Expression?: ((((2*3)*(4*6))*7)+(((7+8)+9)*((2+4)*((7+8)+9))))

Answer:

23*46*7*789++24+78+9+**+

4 in modulo 10

Your program can be tested for additional input we may choose.