c++ - 即使在 pop() 之后，STL stack top() 函数也读取相同的值。

Question

我有一个将前缀字符串转换为中缀的代码。我用过STL堆栈。 测试输入:*/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;
}

现在 o1 应该在遇到第一个操作数时存储 c，而 o2 应该存储 d。 但是我得到的输出如下，

Output

有人可以帮忙吗？

Answer 1

我在您的代码中看到的问题:

在循环中重用op

你已经在循环开始之前为op分配了内存。

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

然后您在 for 循环中使用相同的内存。

在 if block 中:

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

并在 else block 中。

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

每次都需要为op分配内存。

将 strcat 与非空终止的字符串一起使用

在 else block 中，您有:

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

这些行中的第一行将 temp 的空字符替换为 prefix[i]。此时，temp 不是空终止字符串。上面第三行中对 strcat 的调用导致了未定义的行为。

您需要使用以下内容:

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

混合 malloc 和 new

混合使用 malloc 和 new 并不是您所看到的内存问题的原因，但最好坚持使用 new，因为您在 C++ 领域。

这是您的程序的一个修复版本:

#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;
}

更新

通过使用 std::string 而不是 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;
}