Help With Simple Equation Parsing

[skatamatic]

I'm writing a class for simple equation parser. I've completed the - and + operators, and am currently working on implementing brackets. They seem to work most of the time, except I occassionally get strange results, such as with 10 - ((10 - 20) + (10 - 20)) returns 40! It should only be 30 >.< ! I've tried stepping through the code to see what was going wrong, and I know for sure that I'm handling brackets incorrectly. I think I'm on the right track for this, but any help would be much appreciated.

This is the function cpp:

#include "Function.h"


CFunction::~CFunction(void)
{
}

int CFunction::GetNextValue(int & i)
{
	string sBuffer;
	char szFormula[255];
	strcpy_s(szFormula, 255, _sFunc.c_str());
	bool numStream(false);
	for (i = i; i < strlen(szFormula); ++i)
    {
       if (isdigit(szFormula[i]))
       {
		   //add the digit to the buffer
            numStream = true;
			sBuffer += szFormula[i];
       }
	   if (numStream && (!isdigit(szFormula[i]) || i == strlen(szFormula) - 1))
	   {
		   return atoi(sBuffer.c_str()); //return the buffer, converted to int
	   }
	   if (szFormula[i] == '(')
	   {//solve what's inside brackets first!
		   if (numStream)
			   throw exception ("Bracket error");
		   string tmp(ToCloseBracket(i));
		   return CFunction(tmp).Solve();
	   }
	}
	//error flag
	return -1;
}

string CFunction::ToCloseBracket(int & iIndex)
{
//problem function!!!***********************
	string sBuffer = "";
	int iCount(0), iCount2(0);
	for (int i(iIndex); i < strlen(_sFunc.c_str()); ++i)
	{
		if (_sFunc[i] == '(')
			iCount++;
	}
	while (iCount2 < iCount)
	{
		if (_sFunc[iIndex++] == ')')
			iCount2++;
		else
			sBuffer += _sFunc[iIndex];
	}
	return sBuffer;
}

int CFunction::Solve(char var)
{
	int i(0),
		iTmpVal(0),
		iReturn(0);
	char op(0);
	iReturn = GetNextValue(i);
	while (i < strlen(_sFunc.c_str()) - 1)
	{
		op = GetNextOp(i);
		iTmpVal = GetNextValue(i);
		switch (op)
		{
		case '+': iReturn += iTmpVal; break;
		case '-': iReturn -= iTmpVal; break;
		default: break;
		}
	}
	return iReturn;
}

char CFunction::GetNextOp(int & i)
{
	for (i = i; i < strlen(_sFunc.c_str()); ++i)
       if (_sFunc[i] == '+' || _sFunc[i] == '-' || _sFunc[i] == '*' || _sFunc[i] == '/')
		   return _sFunc[i];
	//error flag
	return -1;
}

This is the header:

#pragma once
#pragma warning(disable: 4018)
#include <iostream>
#include <string.h>
using namespace std;

class CFunction
{
protected:
	string _sFunc;
	int    _iCursor;
	int GetNextValue(int &);
	char GetNextOp(int &);
	string ToCloseBracket(int &);
public:
	bool SetFunc(string);
	int Solve(char = 0);
	CFunction(string s): _iCursor(0)
	{
		_sFunc = s;
	}
	~CFunction(void);
};

and here is the main() implementation

#include <string>
#include <iostream>
using namespace std;
#include "Function.h"

int main()
{
	char szBuffer[255];
	string sBuffer = "";
	cout << "Enter formula: ";
	cin.getline(szBuffer, 254);
	sBuffer = szBuffer;
	CFunction myFunc(sBuffer);
	cout << sBuffer << " = " << myFunc.Solve() << endl;
	cin.get();
	return 0;
}

[dougy83]

I wrote an equation parser a few years back, don't have it on me, but I'll try to dig it up for you.

I think the idea I used was to pass through the equation string a few times - the first time assigns a numerical priority to each operator (based on 'BODMAS' - i.e. bracket, orders (powers/exponents), division, multiplication, addition, subtraction). The higher the priority, the sooner the operation is done. I think I increased the base priority (a value I added to the relative priority value given by 'BODMAS') by say 10 when I ran into an open bracket, and decreased it by 10 when I hit a close bracket, that way the operators inside the deepest set of brackets will have the highest priority.

Then running through again to evaluate the highest priority operator, replacing the operator and 2 operands with the result. This loop continues until only a single value is left, which is the answer to the equation.

It was really quick and simple to write (and I was a beginner back then), so if you want to try the above method, have a go. I'll see if I can find the original in the mean time.

[iamthwee]

Google rpn/shunting yard algorithm.

http://www.daniweb.com/code/snippet599.html