C++：我的堆栈顶部发生了什么？

Question

我正在做一个作业，我必须通过使用两个堆栈（一个保存值，一个保存运算符）。

例如，输入 1 + 2 - 3 * 4 / 5 程序应该输出 0.6。

但是，每当我在操作后将值推回 valueStack 时，堆栈顶部的值在退出 doOp() 方法后似乎消失或变成垃圾值。我一直在尝试跟踪和调试，但我仍然不知道为什么会这样。任何帮助或正确方向的观点将不胜感激。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <stack>
#include <cstring>

using namespace std;

stack<char*> operatorStack;
stack<char*> valueStack;
string input;

void repeatOps(char refOp);
void doOp();
int prec(char refOp);

int main(){
    cout << "Enter expression to be evaluated: ";
    getline(cin, input);

    //Parse the string and perform EvalExp() Algorithm
    char *cString = strdup(input.c_str());
    char *token = strtok(cString, " ");
    while(token !=NULL){
        if(isdigit(token[0])){
            valueStack.push(token);
        }
        else{
            repeatOps(*token);
            operatorStack.push(token);
        }   
            token = strtok(NULL, " ");
    }
    repeatOps('$');
    //print out answer
    cout << valueStack.top() << endl;
}

void repeatOps(char refOp){
    while(valueStack.size() > 1 && prec(refOp) <= prec(*operatorStack.top())){
        //debug print statements REMOVE LATER 
        cout << "Printing top of stack in repeatOps before doOp():  " << valueStack.top() << endl;
        doOp();
    }
}

//return precedence of operator
int prec(char refOp){
    if(refOp == '*' || refOp == '/'){
        return 2;
    }
    else if(refOp == '+' || refOp == '-'){
        return 1;
    }
    //Use $ as a special "end of input" token with lowest precedence
    else if(refOp == '$'){
        return -1;
    }
    // if not any of the operators above, it's comparison operator return 0
    else{
        return 0;
    }
}

void doOp(){
    int x = atoi(valueStack.top());
    valueStack.pop(); 
    int y = atoi(valueStack.top());
    valueStack.pop();
    char * op = operatorStack.top();
    operatorStack.pop();

    double doubleReturnValue;
    bool booleanReturnValue;

    //If it's a comparison operator, push true or false and exit function
    if(strncmp(op, "<=", 2) == 0 || strncmp(op, ">=", 2) == 0){
        char trueResult[] = "true";
        char falseResult[] = "false";
        if(strncmp(op, "<=",2)){
            booleanReturnValue = y <= x;
        }
        else{
            booleanReturnValue = y >= x;
        }

        if(booleanReturnValue){
            valueStack.push(trueResult);
        }
        else{
            valueStack.push(falseResult);
        }
        return;
    }

    //Evaluate arithmetic
    if(*op == '+'){
        doubleReturnValue = y + x;
    }
    else if(*op == '-'){
        doubleReturnValue = y - x;
    }

    else if(*op == '*'){
        doubleReturnValue = y * x;
    }

    else if(*op == '/'){
        doubleReturnValue = y / x;
    }
    //convert the result of the operation to char * for the stack
    char returnChar[10];
    sprintf(returnChar, "%.3f", doubleReturnValue);
    //Debug print statements REMOVE LATER
    cout << "Printing return value in doOp() as char array " << returnChar << endl;
    valueStack.push(returnChar);
    cout << "Printing out top of stack after pushing in doOp(): " << valueStack.top() << endl << endl;
}

Answer 1

如果我没记错的话，您的问题是您将本地字符数组压入堆栈。 stack<char*>不会保存字符串，会保存这些字符串的内存地址。当你将 returnChar 压入堆栈时，只保存地址，所以一旦你离开范围并且删除 returnChar 数组，保存的内存地址指向 freed/unused/junk 内存。

解决此问题的最简单方法是使用 stack<string> 而不是 stack<char*>。 STL 中的字符串将确保复制整个字符串，而不仅仅是局部变量的地址。

Answer 2

这里的这部分没有如你所料的那样工作：

char *token = strtok(cString, " ");
while(token !=NULL){
    if(isdigit(token[0])){
        valueStack.push(token);
    }

问题在于 strtok returns 的指针是一个临时指针，将在下一次调用 strtok.

时指向垃圾

为了保存结果，您需要对令牌

执行strdup

valueStack.push(strdup(token));

尽管我强烈建议您使用 std::string 而不是堆栈中的指针来避免内存泄漏并避免使用 C-function 分配内存。

std::stack<std::string> valueStack;
...
valueStack.push(token);

C++：我的堆栈顶部发生了什么？

C++: What is happening to the top of my stack?

c++

stack

std