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:
- "a1 = a2" and "b1 = b2", in this case we have an infinite number of solutions as any value of x will satisfy the equation.
- "a1 = a2" and "b1 != b2", then we have no solutions as no value of x will ever satisfy the equation.
- "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;
}
