Question

Please use C++:

Data Abstraction, Bags and Stacks:

1. Define a class DoublyLinkedBag that implements the ADT BagInterface by using a doubly linked chain, as shown in Figure 4-10 of your textbook. You will also need to define the class Node described in Excercise 10 of Chapter 4. Your solution to this problem requires the creation/development of four files: Node.h, Node.cpp, DoublyLinkedBag.h and DoublyLinkedBag.cpp. This repository already contains BagInterface.h that contains the declaration of the BagInterface needed by this problem.

2. Convert the following infix expressions to postfix form by using the algorithm given in Chapter 6.

   1. a - b + c
   2. a / (b * c)
   3. (a + b) * c
   4. a / b / c - (d + e) * f
   5. a - (b + c * d) / e

3. Create a new file named question4.h and write a function named isPalindrome that returns a bool value and takes one parameter by constant reference of type std::string. This function must use an instance of ArrayStack to test whether the given string is a palindrome. It shall return true if the given string is a palindrome and false otherwise.

4. Discuss the advantages and disadvantages of an array-based implementation of the ADT stack as compared to a link-based implementation.

Answer 1

PREFIX TO POSTFIX

#include <iostream> 
#include <stack> 

using namespace std; 
bool isOperator(char x) {    
switch (x) {       
   case '+':      
   case '-':      
   case '/':       
​​​​​   case '*':      
 return true;  
  }    
return false; 
} 

string convertToPostfix(string prefix) {    
stack<string> expression;    
int length = prefix.size();  
  for (int i = length - 1; i >= 0; i--) {      
 if (isOperator(prefix[i])) {          string op1 = expression.top();          expression.pop();          string op2 = expression.top();          expression.pop();          string temp = op1 + op2 + prefix[i];          expression.push(temp);      
 }      
 else          expression.push(string(1, prefix[i]));   
 }   
 return expression.top();
 }

 int main() {    
string prefix = "/+XY+NM";    cout<<"Prefix expression : "<<prefix<<endl;    
cout<<"Postfix expression : "<<convertToPostfix(prefix);    return 0; }

INFIX TO POSTFIX

#include<iostream>
#include<stack>
#include<locale>     
 //for function isalnum()
using namespace std;

int preced(char ch) {
   if(ch == '+' || ch == '-') {
      return 1;              //Precedence of + or - is 1
   }else if(ch == '*' || ch == '/') {
      return 2;            //Precedence of * or / is 2
   }else if(ch == '^') {
      return 3;            //Precedence of ^ is 3
   }else {
      return 0;
   }
}

string inToPost(string infix ) {
   stack<char> stk;
   stk.push('#');               //add some extra character to avoid underflow
   string postfix = "";         //initially the postfix string is empty
   string::iterator it;

   for(it = infix.begin(); it!=infix.end(); it++) {
      if(isalnum(char(*it)))
         postfix += *it;      //add to postfix when character is letter or number
      else if(*it == '(')
         stk.push('(');
      else if(*it == '^')
         stk.push('^');
      else if(*it == ')') {
         while(stk.top() != '#' && stk.top() != '(') {
            postfix += stk.top(); //store and pop until ( has found
            stk.pop();
         }
         stk.pop();          //remove the '(' from stack
      }else {
         if(preced(*it) > preced(stk.top()))
            stk.push(*it); //push if precedence is high
         else {
            while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {
               postfix += stk.top();        //store and pop until higher precedence is found
               stk.pop();
            }
            stk.push(*it);
         }
      }
   }

   while(stk.top() != '#') {
      postfix += stk.top();        //store and pop until stack is not empty.
      stk.pop();
   }

   return postfix;
}

int main() {
   string infix = "a-b+c";
​​​   cout << "Postfix Form Is: " << inToPost(infix) << endl;
}

Postfix: ab-c+

Screenshot of implementation and output.

you run other expression and get postfix expression. if you don't manually enter just insert one line for user entry.

For more detail comment.