Problem CALCULATOR Input: A fully parenthesized expression E, where each operand

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>
#include <string>
#include<sstream>

using namespace std;

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];
   }
};

int main() {
   string infixExpr;
   string postfixExpr = "";
   cout << "Enter infix expression:" << endl;
   cin >> infixExpr;

   //converting to postfix

   //read from the input
   int N = infixExpr.size();

   //strncpy(a, infixExpr.c_str(), N);
   STACK ops(N);
   char ch;

   for (int i = 0; i < N; i++) {
       if (infixExpr[i] == ')') {
           ch = ops.pop();
           cout << ch << " ";
           postfixExpr.push_back(ch);
       }
       if ((infixExpr[i] == '+') || (infixExpr[i] == '*')   || (infixExpr[i] == '^'))
           ops.push(infixExpr[i]);
       if ((infixExpr[i] >= '0') && (infixExpr[i] <= '9')) {
           cout << infixExpr[i] << " ";
           postfixExpr.push_back(infixExpr[i]);
       }
   }
   cout << endl;

   cout << postfixExpr <<endl;
   //evaluate post fix expression
   N = postfixExpr.size();
   STACK save(N);
   int result;
   int num;
   int count = 0;
    string temp = "";
   for (int i = 0; i < N; i++) {
   //   cout << " Expr[i] " << postfixExpr[i] << endl;
       if (postfixExpr[i] == '+')
           save.push((save.pop() + save.pop()) % 10);
       if (postfixExpr[i] == '*')
           save.push((save.pop() * save.pop()) % 10);
       if (postfixExpr[i] == '^') {
           count = save.pop() - '0';
           num = save.pop() - '0';
//           cout << result << "- " <<"-" <<count<<endl;
           result = 1;
           for(int j = 1; j <= count; j++) {
               result = result * num;
               result = result % 10;
           }

           stringstream convert;
           convert << result;//add the value of Number to the characters in the stream

           temp = convert.str();//set Result to the content of the stream
           //temp +=(result);
           //cout << " ch = " <<temp << " : " << result << " -- " <<endl;
            save.push(temp[0]);
       }
       if ((postfixExpr[i] >= '0') && (postfixExpr[i] <= '9')) {
           //cout << postfixExpr[i] << " ## ";
           save.push(postfixExpr[i]);
       }
   }
   cout << save.pop() << endl;

   return 1;
}

---output---

Enter infix expression:
((((2+5)*7)+((9*3)*2))^2)
2 5 + 7 * 9 3 * 2 * + 2 ^
25+7*93*2*+2^
9

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.