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??