The expression tree shown below has three kinds of nodes: (1) leaves with an int

Question

The expression tree shown below has three kinds of nodes:

(1) leaves with an integer value,
(2) unary nodes with an operator and a single subtree
(3) binary nodes with an operator and two subtrees.

           *
   /
   /
   -   +
   |   /
   | /
   5   3 4

The goal is to construct and print expression trees in paranthesized
prefix notation, where parentheses enclose an operator and its
operands. For example, the above tree must be printed as

   ( * ( - 5) ( + 3 4) )

Develop the program fragment given below into a C++ program. Note
that a tree prints itself by asking its root node to print itself.
Function print in class Node is virtual, so a derived class can supply
a function body to be executed when print is called.

#include <stdio.h>
class Node {
public:
virtual void print() {}
};
...
class Tree {
   Node *root;
public:
       Tree(int);
       Tree(char op, Tree *p);
       Tree(char op, Tree *l, Tree *r);
   void print() { root->print(); }
};
main() {
   Tree t1('-', new Tree(5));
   Tree t2('+', new Tree(3), new Tree(4));
   Tree t('*', &t1, &t2);
   t.print();
   printf(" ");
}

Explanation / Answer

Compiled and Executed Code..Working fine..

#include <iostream.h>
#include <string.h>
#include <ctype.h>
const int MAX123 = 50 ;
class infix
{
   private :
       char target[MAX123], stack[MAX123] ;
       char *s123, *t123;
       int top ;
   public :
       infix( ) ;
       void setexpr123 ( char *str ) ;
       void push ( char c ) ;
       char pop( ) ;
       void convert( ) ;
       int priority_iooo ( char c ) ;
       void show( ) ;
} ;
infix :: infix( )
{
   top = -1 ;
   strcpy ( target, "" ) ;
   strcpy ( stack, "" ) ;
   t123 = target ;
   s123 = "" ;
}
void infix :: setexpr123 ( char *str )
{
   s123 = str ;
}
void infix :: push ( char c )
{
   if ( top == MAX123 )
       cout << " Stack is full " ;
   else
   {
       top++ ;
       stack[top] = c ;
   }
}
char infix :: pop( )
{
   if ( top == -1 )
   {
       cout << " Stack is empty " ;
       return -1 ;
   }
   else
   {
       char item = stack[top] ;
       top-- ;
       return item ;
   }
}
void infix :: convert( )
{
   while ( *s123 )
   {
       if ( *s123 == ' ' || *s123 == ' ' )
       {
           s123++ ;
           continue ;
       }
       if ( isdigit ( *s123 ) || isalpha ( *s123 ) )
       {
           while ( isdigit ( *s123 ) || isalpha ( *s123 ) )
           {
               *t123 = *s123 ;
               s123++ ;
               t123++ ;
           }
       }
       if ( *s123 == '(' )
       {
           push ( *s123 ) ;
           s++ ;
       }
       char opr ;
       if ( *s123 == '*' || *s123 == '+' || *s123 == '/' || *s123 == '%' || *s123 == '-' || *s123 == '$' )
       {
           if ( top != -1 )
           {
               opr = pop( ) ;
               while ( priority_iooo ( opr ) >= priority_iooo ( *s123 ) )
               {
                   *t = opr ;
                   t++ ;
                   opr = pop( ) ;
               }
               push ( opr ) ;
               push ( *s123 ) ;
           }
           else
               push ( *s123 ) ;
           s123++ ;
       }
       if ( *s123 == ')' )
       {
           opr = pop( ) ;
           while ( ( opr ) != '(' )
           {
               *t = opr ;
               t++ ;
               opr = pop( ) ;
           }
           s123++ ;
       }
   }
   while ( top != -1 )
   {
       char opr = pop( ) ;
       *t = opr ;
       t++ ;
   }
   *t = '' ;
}
int infix :: priority_iooo ( char c )
{
   if ( c == '$' )
       return 3 ;
   if ( c == '*' || c == '/' || c == '%' )
       return 2 ;
   else
   {
       if ( c == '+' || c == '-' )
           return 1 ;
       else
           return 0 ;
   }
}
void infix :: show( )
{
   cout << target ;
}
void main( )
{
   char expr123[MAX123] ;
   infix q123 ;

   cout << " Enter an expression in infix form: " ;
   cin.getline ( expr123, MAX123 ) ;

   q123.setexpr123 ( expr123 ) ;
   q123.convert( ) ;

   cout << " The postfix expr123ession is: " ;
   q123.show( ) ;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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