STL stack top() function reads same value even after pop().

Question

I have a code for converting prefix string to infix. I have used stl stack. Test input : */ab+-cde

#include<iostream>
#include<stack>
#include<string.h>
#include<stdlib.h>
using namespace std;
int main()
{
    stack<char*> s;
    char prefix[100],c;
    int l,i,flag[27]={0},pos;
    char *o1,*o2,*op,temp[10];
    cout<<"Prefix expression : ";
    cin>>prefix;
    l=strlen(prefix);
    op=(char *)malloc(sizeof(char)*10);
    o1=new char[10];
    o2=new char[10];
    for(i=l-1;i>=0;i--)
    {
        if(prefix[i]>=97 && prefix[i]<=122)
        {
            if(i!=l-1) cout<<s.top()<<endl;
            cout<<"Operand"<<endl;  
            temp[0]=prefix[i];
            temp[1]='\0';
            strcpy(op,temp);
            s.push(op);
        }
        else
        {
            cout<<"Operator"<<endl;
            cout<<"Top element : "<<s.top()<<endl;
            o1=s.top();
            strcpy(temp,o1);
            s.pop(); 
            cout<<"Top element : "<<s.top()<<endl;
            temp[strlen(temp)]=prefix[i];
            o2=s.top();
            strcat(temp,o2);
            s.pop();
            temp[strlen(temp)]='\0';
            //cout<<o1<<" "<<o2<<endl;
            strcpy(op,temp);
            s.push(op);
            cout<<op<<endl;
        }
    }
    o1=s.top();
    s.pop();
    cout<<"Evaluated expression is "<<o1<<endl;
    return 0;
}

Now the o1 is supposed to store c when the first operand is encountered and o2 is supposed to store d. But the output I get is as follows,

Output

Can someone please help?

Answer 1

Problems I see in your code:

Reusing op in the loop

You have allocated memory for op before the start of the loop.

op=(char *)malloc(sizeof(char)*10);

and then you are using the same memory in the for loop.

In the if block:

        strcpy(op,temp);
        s.push(op);

and in the else block.

        strcpy(op,temp);
        s.push(op);

You'll need to allocate memory for op each time.

Using strcat with a string that is not null terminated

In the else block, you have:

        temp[strlen(temp)]=prefix[i];
        o2=s.top();
        strcat(temp,o2);

The first of those lines replaces the null character of temp with prefix[i]. At that point, temp is not a null terminated string. The call to strcat in the third line above leads to undefined behavior.

You need to use something along the lines of:

        char temp2[2] = {0};
        temp2[0] = prefix[i];
        strcat(temp, temp2);
        o2=s.top();
        strcat(temp,o2);

Mixing malloc and new

Mixing malloc and new is not the cause of the memory issues you are seeing but it is better to stick to using new since you are in C++ land.

Here's a version of your program with the fixes:

#include<iostream>
#include<stack>
#include<string.h>
#include<stdlib.h>
using namespace std;
int main()
{
   stack<char*> s;
   char prefix[100];
   int l,i;
   char *o1,*o2,*op,temp1[10],temp2[10];
   cout<<"Prefix expression : ";
   cin>>prefix;
   l=strlen(prefix);
   o1=new char[10];
   o2=new char[10];
   for(i=l-1;i>=0;i--)
   {
      if(prefix[i]>=97 && prefix[i]<=122)
      {
         if(i!=l-1) cout<<s.top()<<endl;
         cout<<"Operand"<<endl;  
         temp1[0]=prefix[i];
         temp1[1]='\0';
         op = new char[10];
         strcpy(op,temp1);
         s.push(op);
         cout<<"Symbol"<<endl;
         cout<<"Top element : "<<s.top()<<endl;
      }
      else
      {
         cout<<"Operator"<<endl;
         cout<<"Top element : "<<s.top()<<endl;
         o1=s.top();
         strcpy(temp1,o1);
         s.pop(); 
         cout<<"Top element : "<<s.top()<<endl;
         temp2[0]=prefix[i];
         temp2[1]='\0';

         strcat(temp1,temp2);
         o2=s.top();
         strcat(temp1,o2);
         s.pop();
         op = new char[10];
         strcpy(op,temp1);
         s.push(op);
         cout<<op<<endl;
      }
   }
   o1=s.top();
   s.pop();
   cout<<"Evaluated expression is "<<o1<<endl;
   return 0;
}

Update

You can avoid the hassles of allocating and deallocating memory for your strings by using std::string instead of char*.

#include <iostream>
#include <string>
#include <stack>
#include <cstring>

using namespace std;

void test(char prefix[])
{
   stack<std::string> s;
   int l,i;
   char temp[10] = {0};
   std::string op;

   l = std::strlen(prefix);
   for(i=l-1;i>=0;i--)
   {
      if(prefix[i]>=97 && prefix[i]<=122)
      {
         if(i!=l-1) cout<<s.top()<<endl;
         cout<<"Operand"<<endl;  
         temp[0]=prefix[i];
         s.push(temp);
         cout<<"Symbol"<<endl;
         cout<<"Top element : "<<s.top()<<endl;
      }
      else
      {
         cout<<"Operator"<<endl;
         cout<<"Top element : "<<s.top()<<endl;

         op = s.top();
         s.pop(); 

         cout<<"Top element : "<<s.top()<<endl;
         temp[0]=prefix[i];

         op += temp;

         op += s.top();
         s.pop();

         s.push(op);
         cout<<op<<endl;
      }
   }
   op=s.top();
   s.pop();
   cout<<"Evaluated expression is "<<op<<endl;
}

int main()
{
   char prefix[100];
   cout<<"Prefix expression : ";
   cin>>prefix;
   test(prefix);
   return 0;
}