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

Question

I am working on an assignment where I have to evaluate an arithmetic expression which may have the comparison operators <= and >= by using two stacks (one to hold the values and one to hold the operators).

Eg., Input 1 + 2 - 3 * 4 / 5 and the program should output 0.6.

However, whenever I push a value back to the valueStack after an operation, that value at the top of the stack seems to disappear or turn into a junk value after it exits the doOp() method. I've been trying to trace and debug but I still have no idea why this is happening. Any help or a point in the right direction would be much appreciated.

Code:

#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

If I'm not wrong, your problem is that you are pushing a local char array on the stack. stack<char*> won't save strings, it will save the memory addresses of these strings. When you push returnChar onto the stack, only the address is saved, so once you get out of the scope and the returnChar array is deleted, the saved memory address points into freed/unused/junk memory.

The easiest way to fix this would be to use stack<string> instead of stack<char*>. The strings in the STL will ensure that the whole string is copied, not only the address to a local variable.

Answer 2

This part here doesn't work as you expect:

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

The problem lies in that the pointer that strtok returns is a temporary pointer which will point to garbage by the next call to strtok.

In order to save the result you need to do a strdup on the token

valueStack.push(strdup(token));

Although I would strongly suggest you use std::string instead instead of pointers in your stack to avoid memory leaks plus avoid using a C-function to allocate memory.

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