UVa 533 - Equation Solver

UVa Problem

This problem is about how to solve a linear equation. Since we're sure that it will always be a linear equation, the solution is simple.

we have a complex equation like this "(42-6*7)*x=2*5-10"

my solution divides the equation into two expressions around the "=" operator.
then we reduce each expression into one of the form "a * x + b" where "a" and "b" are integers.

so we reduces the whole equation to "a1 * x + b1 = a2 * x + b2"

there are three possibilities:

1. "a1 = a2" and "b1 = b2", in this case we have an infinite number of solutions as any value of x will satisfy the equation.
2. "a1 = a2" and "b1 != b2", then we have no solutions as no value of x will ever satisfy the equation.
3. "a1 != a2", then we can calculate "x" simply as "x" = (b2 - b1) / (a1 - a2).

I wrote a simple recursive-decent parser for the problem and kept reducing the expression as I go up in the parse tree.

Code:

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <sstream>

using namespace std;

enum TokenType
{
   TOKEN_INT,
   TOKEN_EQ,
   TOKEN_X,
   TOKEN_LP,
   TOKEN_RP,
   TOKEN_PLUS,
   TOKEN_MINUS,
   TOKEN_MUL,
   TOKEN_END
};

class Token
{
public:
   Token(TokenType tokType) : mType(tokType)
   {

   }
   TokenType getType()
   {
      return mType;
   }
private:
   TokenType mType;
};

class IntToken : public Token
{
public:
   IntToken(int value) : mValue(value),
   Token(TOKEN_INT)
   {

   }
   int getValue()
   {
      return mValue;
   }
private:
   int mValue;
};

class Lexer
{
public:
   Lexer(istream& iStream) : mStream(iStream)
   {

   }
   Token* getNextToken()
   {
      int ch = mStream.get();
      char ccc = (char)ch;
      while(ch == ' ')
         ch = mStream.get();

      switch(ch)
      {
         case '=':
            return new Token(TOKEN_EQ);
            break;
         case '+':
            return new Token(TOKEN_PLUS);
            break;
         case '-':
            return new Token(TOKEN_MINUS);
            break;
         case '*':
            return new Token(TOKEN_MUL);
            break;
         case 'x':
            return new Token(TOKEN_X);
            break;
         case '(':
            return new Token(TOKEN_LP);
            break;
         case ')':
            return new Token(TOKEN_RP);
            break;
         case EOF:
            return new Token(TOKEN_END);
            break;
         default:
            if(ch >= '0' && ch <= '9')
            {
               int number = 0;

               while(ch >= '0' && ch <= '9')
               {
                  number *= 10;
                  number += ch - '0';
                  ch = mStream.get();
               }

               mStream.putback(ch);

               return new IntToken(number);
            }
            else
            {
               return new Token(TOKEN_END);
            }
            break;

      }
   }
private:
   istream& mStream;
};

class Solver
{
public:
   Solver(istringstream& exprStream):
      mLexer(exprStream), mCurrTok(0)
   {
      mCurrTok = mLexer.getNextToken();
      pair<int, int> result = expr();
      m_x = result.first;
      m_num = result.second;
   }


   int get_xFactor()
   {
      return m_x;
   }

   int get_numFactor()
   {
      return m_num;
   }

private:

   pair<int, int> expr()
   {
      pair<int, int> result = term();
      pair<int, int> tmp = rExpr();
      result.first += tmp.first;
      result.second += tmp.second;
      return result;
   }

   pair<int, int> rExpr()
   {
      pair<int, int> result = make_pair(0, 0);
      if(mCurrTok->getType() == TOKEN_PLUS)
      {
         match(TOKEN_PLUS);
         pair<int, int> tmp = term();
         result.first += tmp.first;
         result.second += tmp.second;
         tmp = rExpr();
         result.first += tmp.first;
         result.second += tmp.second;
      }
      else if (mCurrTok->getType() == TOKEN_MINUS)
      {
         match(TOKEN_MINUS);
         pair<int, int> tmp = term();
         result.first -= tmp.first;
         result.second -= tmp.second;
         tmp = rExpr();
         result.first += tmp.first;
         result.second += tmp.second;
      }
      return result;
   }

   pair<int, int> term()
   {
      pair<int, int> tmp1 = factor();
      pair<int, int> tmp2 = rTerm();

      return make_pair(tmp1.first * tmp2.second +
            tmp1.second * tmp2.first,
            tmp1.second * tmp2.second);

   }

   pair<int, int> rTerm()
   {
      if(mCurrTok->getType() == TOKEN_MUL)
      {
         match(TOKEN_MUL);
         return term();

      }
      return make_pair(0, 1);;
   }

   pair<int, int> factor()
   {
      if(mCurrTok->getType() == TOKEN_X)
      {
         match(TOKEN_X);
         return make_pair(1, 0);
      }
      else if(mCurrTok->getType() == TOKEN_INT)
      {
         IntToken* intTok = (IntToken*)mCurrTok;
         int val = intTok->getValue();
         match(TOKEN_INT);
         return make_pair(0, val);
      }
      else
      {
         match(TOKEN_LP);
         pair<int, int> exprVal = expr();
         match(TOKEN_RP);
         return exprVal;
      }
   }

   bool match(TokenType tokType)
   {
      if(mCurrTok->getType() == tokType)
      {
         delete mCurrTok;
         mCurrTok = mLexer.getNextToken();
         return true;
      }
      else
      {
         // Handle errors
      }

      return false;
   }
private:
   Lexer mLexer;
   Token *mCurrTok;
   int m_num;
   int m_x;
};

int main(int argc, char* argv[])
{

   string strLine;
   int iEqu = 1;
   bool firstTime = true;

   while(cin >> strLine)
   {
      istringstream inputStream(strLine);
      int iPos = strLine.find_first_of('=');
      string expr1 = strLine.substr(0, iPos);
      string expr2 = strLine.substr(iPos+1);

      istringstream strStream1(expr1);
      istringstream strStream2(expr2);

      Solver s1(strStream1);
      Solver s2(strStream2);

      if(!firstTime)
         cout << '\n';
      else
         firstTime = false;

      cout << "Equation #" << iEqu << endl;

      if(s1.get_xFactor() == s2.get_xFactor())
      {
         if(s1.get_numFactor() == s2.get_numFactor())
         {
            cout << "Infinitely many solutions.\n";
         }
         else
         {
            cout << "No solution.\n";
         }
      }
      else
      {
         double x = (double)(s2.get_numFactor() -
               s1.get_numFactor())/
               (double)(s1.get_xFactor() -
               s2.get_xFactor());
         
         printf("x = %.6f\n", x);
      }
      ++iEqu;
   }
   return 0;
}