Thread: Binary Expression Trees problem

I'm working on a program to print binary expression trees in a post-fix (A B +) and in-fix (A + B) manner after inputting the data in a pre-fix (+ A B) manner. The code is done and compiles, but I'm having a bit of a problem getting the program to do one important thing: output. Input is fine, and output from the main function is fine. However, output from the expression tree functions is not fine. Were I to enter "+ A B", it prints nothing. What's in the code that's making it do that?

EDIT: Fixed the second issue, the output one still applies though.

The code is all below.

Code:

// Trey Brumley
// Discrete Structures
// 23 April, 2014
// Program 4 - Binary Expression Trees
// ===================================


#include <iostream>
using namespace std;


struct node
{
    char data;
    node *left;
    node *right;
};


void ExpTree(char *suffix);
void preOrder(node *tree);
void postOrder(node *tree);
void inOrder(node *tree);


char prefix[35];
int top=-1;
node *arr[35];


int main()
{
    char choice = 'Y';


    if (choice == 'Y')
    {
        cout<<"Please enter a Prefix Expression:  ";
        cin>>prefix;


        //Creation of Expression Tree
        ExpTree(prefix);


        //Traversal Operation on expression tree
        cout << "In-Order Traversal:   ";
        inOrder(arr[0]);
        cout >> endl;


        cout << "Pre-Order Traversal:  ";
        preOrder(arr[0]);
        cout << endl;


        cout << "Post-Order Traversal: ";
        postOrder(arr[0]);
        cout << endl;


        cout << "Would you like to enter another question (Y or N)?  ";
        cin >> choice;
        choice = toupper(choice);
    }
    else if (choice != 'Y' && choice != 'N')
    {
        cout << "ERROR:  Invalid choice.  Please enter only Y or N:  ";
        cin >> choice;
        choice = toupper(choice);
    }
    else
    {
    system("pause");
    return 0;
    }
}


void push(node *tree)
{
    top++;
    arr[top]=tree;
}


node *pop()
{
    top--;
    return(arr[top+1]);
}


int  r(char c)
{ //for checking symbol is operand or operatorif(inputchar=='+' || inputchar=='-' || inputchar=='*' || inputchar=='/')
    if (c == '+' || c == '-' || c == '/' || c== '*' || c == '%')
        return(-1);
    else if(c >= 'a' || c <= 'z')
        return(1);
    else if(c >= 'A' || c <= 'Z')
        return(1);
    else if (c == ' ')
        return(0);
    else
        return(-99);  //for error
}


void ExpTree(char *suffix)
{
    char symbol;
    node *newl,*ptr1,*ptr2;
    int flag;
    symbol = suffix[0];
    for(int i = 1; symbol !=NULL; i++)
        {
            flag = r(symbol);
            if(flag == 1)
                {
                    newl = new node;
                    newl->data = symbol;
                    newl->left = NULL;
                    newl->right = NULL;
                    push(newl);
                }
            else if (flag == -1)
                {    //If the symbol is operator//pop two top elements.
                    ptr1=pop();
                   ptr2=pop();
                    newl = new node;
                    newl->data = symbol;
                   newl->left = ptr2;
                    newl->right = ptr1;
                    push(newl);
                }
            else if (flag == 0)
                symbol = suffix[i]; // If symbol is a space, skip.
            symbol=suffix[i];
        }
}


void preOrder(node *tree)
{
    if( tree!=NULL)
    {
        cout << tree->data << " ";
        preOrder(tree->left);
        preOrder(tree->right);
    }
}


void inOrder(node *tree)
{
    if( tree!=NULL)
    {
        inOrder(tree->left);
        cout << tree->data << " ";
        inOrder(tree->right);
    }
}


void postOrder(node *tree)
{
    if( tree!=NULL)
    {
        postOrder(tree->left);
        postOrder(tree->right);
        cout << tree->data << " ";
    }
}

> Were I to enter "+ A B", it prints nothing. What's in the code that's making it do that?

Given that the first thing it does in your parser is
> else if (flag == -1)
> //If the symbol is operator//pop two top elements.

I'd say your stack is trashed and you're storing the data in unexpected places.

You seem to be equating "not crashing" with "working", and this is never true.

In future, run the code in the debugger and really follow through what the code is actually doing.

Code:

$ gdb ./a.out 
(gdb) break 43
Breakpoint 1 at 0x400a3a: file bar.cpp, line 43.
(gdb) run
Starting program: /home/sc/Documents/a.out 
Please enter a Prefix Expression:  + A B

Breakpoint 1, main () at bar.cpp:43
43              ExpTree(prefix);
(gdb) print arr
$1 = {0x0 <repeats 35 times>}
(gdb) s
ExpTree (suffix=0x6022c0 "+") at bar.cpp:114
114         symbol = suffix[0];
(gdb) n
115         for(int i = 1; symbol !=0; i++)
(gdb) 
117                 flag = r(symbol);
(gdb) 
118                 if(flag == 1)
(gdb) 
126                 else if (flag == -1)
(gdb) 
128                         ptr1=pop();
(gdb) s
pop () at bar.cpp:89
89          top--;
(gdb) fin
Run till exit from #0  pop () at bar.cpp:89
0x0000000000400c8b in ExpTree (suffix=0x6022c0 "+") at bar.cpp:128
128                         ptr1=pop();
Value returned is $2 = (node *) 0x0
(gdb) n
129                        ptr2=pop();
(gdb) 
130                         newl = new node;
(gdb) print top
$3 = -3