Using the book C++ programming: program design including data structures D.S Mal

Question

Using the book C++ programming: program design including data structures D.S Malik 7th edition. Ch17 programming exericse 10 on page 1262. Chegg does have a solution for this however I do not feel it answers it as well as it should, It does not have overloaded operators, etc. I would like to see a revised/new solution to this book exercise

the question:

(Infix to Postfix) Write a program that converts an infix expression into an equivalent postfix expression.
The rules to convert an infix expression into an equivalent postfix expression are as follows:
Suppose infx represents the infix expression and pfx represents the postfix expression. The rules to convert infx into pfx are as follows:
a. Initialize pfx to an empty expression and also initialize the stack. b. Get the next symbol, sym, from infx. b.1. If sym is an operand, append sym to pfx. b.2. If sym is (, push sym into the stack. b.3. If sym is ), pop and append all of the symbols from the stack until the most recent left parentheses. Pop and discard the left parentheses. b.4. If sym is an operator: b.4.1. Pop and append all of the operators from the stack to pfx that are above the most recent left parentheses and have precedence greater than or equal to sym. b.4.2. Push sym onto the stack. c. After processing infx, some operators might be left in the stack. Pop and append to pfx everything from the stack.
In this program, you will consider the following (binary) arithmetic operators: +, -, *, and/. You may assume that the expressions you will process are error free. Design a class that stores the infix and postfix strings. The class must include the following operations: • getInfix: Stores the infix expression. • showInfix: Outputs the infix expression. • showPostfix: Outputs the postfix expression.
Some other operations that you might need are: • convertToPostfix: Converts the infix expression into a postfix expression. The resulting postfix expression is stored in pfx.
1262 | Chapter 17: Stacks and Queues
Copyright 2015 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
C8652_CH17
• precedence: Determines the precedence between two operators. If the first operator is of higher or equal precedence than the second operator, it returns the value true; otherwise, it returns the value false.
Include the constructors and destructors for automatic initialization and dynamic memory deallocation.
Test your program on the following expressions:
a. A + B - C;
b. (A + B ) * C;
c. (A + B) * (C - D);
d. A + ((B + C) * (E - F) - G) / (H - I);
e. A + B * (C + D ) - E / F * G + H;
For each expression, your answer must be in the following form:
Infix Expression: A + B - C; Postfix Expression: A B + C

Explanation / Answer

#include <iostream>
#include <conio.h>
#include<string.h>
#include<stack>
using namespace std;

template <class type> struct Node {
type data;
Node* link;

Node(type x)
{
   data = x;
   link = NULL;
}
};

template <class T> class Stack
{
private:
Node<T>* top;

public:
Stack()
{
   top = NULL;
}

void push(T x)
{
   Node<T>* temp = new Node<T>(x);

   if(top == NULL)
   top = temp;
   else {
   temp->link = top;
   top = temp;
   }
}

bool pop(T& x)
{
   if(top == NULL)
   return false;
   else {
   x = top->data;
   Node<T>* temp = top;
   top = top->link;
   delete temp;
   return true;
   }
}

bool peek(T& x)
{
   if(top == NULL)
   return false;
   else {
   x = top->data;
   return true;
   }
}

void print()
{
   Stack<T> s;
   T k;

   while(pop(k)) {
   cout << k;
   s.push(k);
   }

   while(s.pop(k))
   push(k);
}

~Stack()
{
   T k;
   while(pop(k))
   ;
}
};
struct et
{
char value;
et* left, *right;
};
bool isOperator(char c)
{
if (c == '+' || c == '-' ||
c == '*' || c == '/' ||
c == '^')
return true;
return false;
}

// Utility function to do inorder traversal
void printInfix(et *t)
{
  
if(t)
{
printInfix(t->left);
cout<<t->value;
printInfix(t->right);
}
}

// A utility function to create a new node
et* newNode(int v)
{
et *temp = new et;
temp->left = temp->right = NULL;
temp->value = v;
return temp;
};

// Returns root of constructed tree for given
// postfix expression
et* constructTree(char postfix[])
{
stack<et *> st;
et *t, *t1, *t2;

// Traverse through every character of
// input expression
for (int i=0; i<strlen(postfix); i++)
{
// If operand, simply push into stack
if (!isOperator(postfix[i]))
{
t = newNode(postfix[i]);
st.push(t);
}
else // operator
{
t = newNode(postfix[i]);

// Pop two top nodes
t1 = st.top(); // Store top
st.pop(); // Remove top
t2 = st.top();
st.pop();

// make them children
t->right = t1;
t->left = t2;

// Add this subexpression to stack
st.push(t);
}
}

// only element will be root of expression
// tree
t = st.top();
st.pop();

return t;
}
class InfixPostfix
{
private:
  
  
int postfixSize;
char* variables;
int varNum;
double* varValue;

bool isHigher(char a, char b)
{
   int x, y;

   if(a == '(')
   return false;

   if((a == '+') || (a == '-'))
   x = 1;
   else
   x = 2;

   if((b == '+') || (b == '-'))
   y = 1;
   else
   y = 2;

   return (x >= y);
}

public:
   char* postfix;
   void convertToPostfix(char a[],int);
   void printInfix();
   void printPostfix();
   ~InfixPostfix()
{
   delete[] postfix;
  
   delete[] variables;
   delete[] varValue;
   postfix = variables = NULL;
   varValue = NULL;
}
};
void InfixPostfix::convertToPostfix(char A[], int e){
   postfixSize = 0;
   varNum = 0;
   postfix = new char[e];
   variables = new char[e];
   varValue = new double[e];
   Stack<char> op;
   char cur, temp;
   bool found;

   for(int i = 0; i < e; i++) {
   cur = A[i];
   switch(cur) {
   case '(':
       op.push(cur);
       break;
   case '+':
   case '-':
   case '*':
   case '/':
       if(op.peek(temp))
       while(isHigher(temp, cur)) {
           op.pop(temp);
           postfix[postfixSize++] = temp;
           if(!op.peek(temp))
           break;
       }

       op.push(cur);
       break;

   case ')':
       op.peek(temp);
       while(temp != '(') {
       op.pop(temp);
       postfix[postfixSize++] = temp;
       op.peek(temp);
       }
       op.pop(temp);
       break;

   default:
       postfix[postfixSize++] = cur;

       found = false;

       for(int u = 0; u < varNum; u++)
       if(cur == variables[u])
           found = true;

       if(!found)
       variables[varNum++] = cur;

       break;
   }
   //op.print();
  
  
   }

   while(op.pop(temp))
   postfix[postfixSize++] = temp;

   postfix[postfixSize] = '';
}

  
void InfixPostfix::printPostfix()
{
   cout << " Postfix Expression: " << postfix << endl;
}

int main()
{
char c;
InfixPostfix k;
char infix[100];
int size = 0;
cout << "Enter an infix expression with (?) at the end: ";
cin >> c;
while(c != '?') {
   infix[size++] = c;
   cin >> c;
}
k.convertToPostfix(infix, size);
et* r = constructTree(k.postfix);
cout<<"Infix Expression is :";
printInfix(r);
k.printPostfix();
cout << " ";
getch();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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