Problem CALCULATOR Input: A fully parenthesized expression E , where each operan
ID: 3676874 • Letter: P
Question
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.
Explanation / Answer
#include <iostream.h> // input output stream header file
#include <stdio.h> // standard input output header file
#include <stdlib.h> // standard library header file
#include <string.h> // header file with string function
#include <conio.h> // console input output header file
// the unavoidable global variables - though it is not a good practice to use global variables, unavoidable in
// certain situations!!
// tos = top of stack = initialized to -1
int tos;
// Including the STACK implementation in our program:
class STACK // both declaration and definition of the class
{
private:
char *s; int N;
public:
STACK(int maxN) // constructor
{ s = new char[maxN]; N = 0; }
// member functions
int empty() const
{ return N == 0; }
void push(char item) // insert or push into stack
{ s[N++] = item; }
char pop() // pop or remove from stack
{ return s[--N]; }
};
int size = 90;
// The following program segment converts a given fully
// parenthesized infix expression in a[] to an equivalent
// postfix expression (for +, and *).
//we 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.
void convertFromInFix2PostFix(char *ip) {
char inFixExpr[90] = {NULL};
char postFixExpr[90] = {NULL};
cout << "Input the expression in Infix notation please:";
cin >> inFixExpr;
char openBracket[1] = "(";
char closeBracket[1] = ")";
char openBrkt = '(';
char closeBrkt = ')';
char powerOp = '^'; // Op = operator
char plusOp = '+';
char minusOp = '-';
char multOp = '*' ; // multiply = *
char divideOp = '/';
strcpy(inFixExpr, openBracket);
strcat(inFixExpr, ip);
strcat(inFixExpr, closeBracket);
char operators[5] = {NULL};
char aux[5] = {NULL}; // aux = auxillary = temperory
int indexVar1;
for(indexVar1 = 0; indexVar1 < strlen(inFixExpr); indexVar1++) {
operators[0] = infixExpr[indexVar1];
if (operators[0] == openBrkt) // keep pushing in all characters after the opening bracket
pushIn2Stack(operators[0]);
else if (operators[0] == closeBrkt ) { // once the close bracket has been met start popping out characters from the stack
operators[0] = pop();
while (operators[0] != openBrkt ) {
strcat(postFixExpr, operators);
operators[0] = pop();
} // end while
} // end of else if
else if (operators[0] == powerOp || operators[0] == multOp || operators[0] == divideOp || operators[0] = plusSign || operators[0] = minusSign ) {
if ( operators[0] == multOp || operators[0] == divideOp ) {
aux[0] = pop();
while (aux[0] == powerOp || aux[0] == multOp || aux[0] == divideOp) {
strcat(postFixExpr, aux);
aux[0] = pop();
} // end while
push(aux[0]);
} // end of if operators in * and /
// next test for + and minus
else if (operators[0] == plusOp || operators[0] == minusOp) {
aux[0] = pop();
while (aux[0] != openBrkt ) {
strcat(postFixExpr, aux);
aux[0] = pop();
} // end while
push(aux[0]);
} // end of what ?
push(operators[0]);
} // end of what?
else strcat(postFixExpr, operators);
} // end of what ?
cout << endl << "Post Fix Expression = " << postFixExpr << " ";
} // end of 2nd else if
} // end for index var 1 from 0 to
} // end function conv in 2 post
void segment2() {
//char a[size]; // a[] should be the postfix expression obtained from original expression
char a[90];
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]);
} // end for
cout << save.pop() << endl;
} // end function segment2()
// we are relieved of prototyping when we define the functions above main or above the calling point
int main() {
tos = -1;
// char a[size]; //read from the input a = an array of characters = a string buffer
char a[90];
int N = strlen(a); // N = length of a
STACK ops(N); // instantiate an object named ops of type class STACK with string length N as parameter
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] << " ";
} // end for loop ?
cout << endl;
segment2(); // call function segment 2
} // end main ?
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.