Why is this causing a runaway consumption of memory

Pardon my choice of title, but I was curious as to why my program seems to have a runaway consumption of memory, especially when no dynamic memory was allocated. In this program, I ask the user for an equation to parse, which is taken in as a string, and then assign that string to the EquationParser. I do it like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include "EquationParser.h"
#include <iostream>
#include <string>

using namespace std;

int main()
{
    bool keepGoing = true, keepAsking = true; //allows the user to keep checking equations
    int posOfBadParenthesis, posOfBadDecimal;
    string equation;
    cout << "Welcome to the equation parser!\n"<< endl;
    while (keepGoing)
    {
        cout << "Please enter an equation for me to parse (the variable should be x) :"<<endl;
        cout << "f(x) == ";
        getline(cin, equation);
        //passing this equation to an EquationParser
        EquationParser parser(equation);
        //informing the user about their syntax
        if ((posOfBadParenthesis = parser.validateParentheses()) != -1)
        {
            cout << "Syntax error: Unclosed parenthesis at position " << posOfBadParenthesis <<endl;
            cout << equation << endl;
            //printing ' ' posOfBadParenthesis times
            for (int x = 0; x < posOfBadParenthesis; x++) cout << ' ';
            cout << '^' <<endl;
        }
        if ((posOfBadDecimal = parser.validateDecimalPoint()) != -1)
        {
            cout << "Syntax error: Invalid '.' at position " << posOfBadDecimal <<endl;
            cout << equation << endl;
            //printing ' ' posOfBadDecimal times
            for (int x = 0; x < posOfBadDecimal; x++) cout << ' ';
            cout << '^' <<endl;
        }
        //Prompt the user if they want check another equation
        while (keepAsking)
        {
            cout << "\nWould you like to keep checking equations (Y/N) ?";
            switch(cin.get())
            {
                case 'Y':
                case 'y':
                    cout << endl;   //flush the outputStream
                    keepAsking = false;
                    break;
                case 'N':
                case 'n':
                    keepGoing = false;
                    keepAsking = false; //this may never get executed
                    break;
                default:
                    cout << "Invalid input. Please try again." <<endl;
                    break;
            }
        }
    }

    return 0;
}

The two functions that I call (from the if-statements!) simply return the last-found position of any misuse of '(', ')', '.'. They are defined as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int EquationParser::validateParentheses()
{
    //declare stack
    std::stack<int> positionStackA, positionStackB;
    //for found parentheses '(', ')' in equation
    for(size_t pos = userEquation.find_first_of("()"); pos != userEquation.npos; pos = userEquation.find_first_of("()", pos++))
    {
        if (userEquation[pos] == '(')   //if the found character == '('
        {
            positionStackA.push((int)pos);    //push its position on the stack
        }
        else
        {
            //if the stack is not empty, pop the position of the last-found '(' from the stack
            if (!positionStackA.empty()) positionStackA.pop();
            //else, place the position on another positionStack
            else positionStackB.push((int)pos);
        }
    }
    //if the positionStackA is empty (the user got their syntax correct) return -1 (or what's on the top of PositionStackB)
    //else return the int on the top of the stack
    switch (positionStackA.empty())
    {
        case true:
            return ((positionStackB.empty()) ? -1 : positionStackB.top());
        case false:
            return positionStackA.top();
    }
}

int EquationParser::validateDecimalPoint()
{
    bool properDecimalPoint = true;
    size_t pos = 0;
    char nextChar;
    //while we are not at the end of the string and there is a properDecimalPoint usage
    while ((pos != -1) && (properDecimalPoint))
    {
        pos = userEquation.find_first_of('.', pos++);   //get the position of the '.'
        //check for an integer after the equation
        nextChar = userEquation[pos + 1];
        properDecimalPoint = (((int)nextChar >= 0x30) && ((int)nextChar <= 0x39));
    }
    return (int)pos; //-1 if the '.' were used properly, or the position of the improperly-used '.' otherwise
}


From reading the article on here about string::find_first_of(), the complexity of it is bounded above by (length()-pos)*numberOfDesiredCharacters . From my understanding, a call to string::find_first_of("()", pos) would be roughly equivalent to:

1
2
3
4
5
6
7
int posOfDesiredCharacter = pos;
while(((someString[posOfDesiredCharacter] != '(') && (someString[posOfDesiredCharacter] != ')') ** (someString[posOfDesiredCharacter] != '\0')
{
    posOfDesiredCharacter++;
}
if (someString[posOfDesiredCharacter] == '\0') posOfDesiredCharacter = -1;
//sorry for all those uses of posOfDesiredCharacter 

am I right?

At first glance, it looks as if what I am trying to do is elementary/common, but upon trying to test my program with an equation like 3*x^2-(3*x + 5) the program starts rapidly eating up memory (as if I am throwing stuff on the heap!). Would you say the culprit is my passing of a string (an object) to the constructor, or the find_first_of(), or both??
Last edited on
In other words, should I have just said EquationParser parser(&equation) and just dealt with the string pointer instead??
Last edited on
Pardon my choice of title, but I was curious as to why my program seems to have a runaway consumption of memory,

Why do you say pardon your choice of title? Edit it to reflect the content of your post. What makes you think your program "seems to have a runaway consumption of memory?"


especially when no dynamic memory was allocated.

But, it was. What type of memory do you think containers such as stacks and strings which can hold an arbitrary number of objects use internally?


Would you say the culprit is my passing of a string (an object) to the constructor, or the find_first_of(), or both??

I would say it is impossible to say what the culprit is or even if there is a "culprit" with the code you've supplied.

I have fixed the title (but didn't want to make it sound like I was "asking for handouts"). So, a stack and the string are "on the heap", and I would have to delete them when done?
Last edited on
So, a stack and the string are "on the heap", and I would have to delete them when done?


No they are not. Internally, they use dynamic memory (from the heap.) When the objects (which reside on the stack) are destroyed, the memory they use internally (on the heap) is freed, although conceptually C++ has no notion of heap/stack.

Google RAII.
The program has the same runaway memory consumption effect even in a version of this program where I don't have classes! I have tried passing-by-reference as well! (Oh, and I don't have C++11 compiler, either)

EDIT: I found the error; it was a very simple problem with how I was incrementing pos in the for loop. I should have said (for the iteration-condition) pos = userEquation.find_first_of("()", pos + 1) instead of pos = userEquation.find_first_of("()", pos++). The latter does increment pos, but uses its previous (unincremented) value. In my case, this sticks pos at an unchanging value thus causing an infinite loop.
Last edited on
Topic archived. No new replies allowed.