"x+9–2-4+x = x+5–1+3–x"The output should be 1.
4*x+3*(x-(4*x+x/3))=9
The output should -1.5
I am considering using a stack and pushing each string token onto it as I encounter spaces in the string. If the input was in polish notation then it would have been easier to pop numbers off the stack to get to a result, but I am not sure what approach to take here.
class LinearExp
{
public:
double a;
double b;
LinearExp(double va, double vb) : a(va), b(vb)
{
}
LinearExp(double vb) : a(0.0), b(vb)
{
}
LinearExp(string x) : a(1.0), b(0.0)
{
}
LinearExp& operator =(const LinearExp &other) {
if (this != &other) {
this->a = other.a;
this->b = other.b;
}
return *this;
}
LinearExp& operator +=(const LinearExp &other) {
this->a += other.a;
this->b += other.b;
return *this;
}
LinearExp& operator -=(const LinearExp &other) {
this->a -= other.a;
this->b -= other.b;
return *this;
}
// does not handle x^2 case
LinearExp& operator *=(const LinearExp &other) {
this->a = other.a * this->b + this->a * other.b;
this->b = other.b * this->b;
return *this;
}
// does not handle 1/x case
LinearExp& operator /=(const LinearExp &other) {
this->a /= other.b;
this->b /= other.b;
return *this;
}
};
class Solution {
void evalOne(stack &operands, stack &operators)
{
char op = operators.top();
operators.pop();
LinearExp right = operands.top();
operands.pop();
LinearExp left = operands.top();
operands.pop();
switch (op) {
case '+':
left += right;
operands.push(left);
break;
case '-':
left -= right;
operands.push(left);
break;
case '*':
left *= right;
operands.push(left);
break;
case '/':
left /= right;
operands.push(left);
break;
}
}
bool hasPrecedence(char op1, char op2)
{
if (op2 == '(' || op2 == ')') return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
LinearExp Eval(string expr)
{
stack operands;
stack operators;
for(char c : expr) {
if (c >= '0' && c <= '9')
operands.push(LinearExp(c - '0'));
else if (c == 'x')
operands.push(LinearExp("x"));
else if (c == '(')
operators.push(c);
else if (c != ')') {
while(operators.size() > 0 && hasPrecedence(c, operators.top()))
evalOne(operands, operators);
operators.push(c);
}
else {
char op;
while((op = operators.top()) != '(')
evalOne(operands, operators);
operators.pop();
}
}
while(operators.size() > 0)
evalOne(operands, operators);
return operands.top();
}
public:
double SolveX(const string &expr) {
int equalPos = expr.find('=');
string left = expr.substr(0, equalPos);
string right = expr.substr(equalPos+1);
LinearExp leftExpr = Eval(left);
LinearExp rightExpr = Eval(right);
return (double)(rightExpr.b - leftExpr.b)/(leftExpr.a - rightExpr.a);
}
};
class Solution2 {
void evalOne(stack &operands, stack &operators)
{
char op = operators.top();
operators.pop();
int right = operands.top();
operands.pop();
int left = operands.top();
operands.pop();
if (op == '+')
operands.push(left + right);
else if (op == '-')
operands.push(left - right);
else if (op == '*')
operands.push(left * right);
else if (op == '/')
operands.push(left / right);
}
bool hasPrecedence(char op1, char op2)
{
if (op2 == '(' || op2 == ')') return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
int Eval(string expr, int replace)
{
stack operands;
stack operators;
for(char c : expr) {
if (c >= '0' && c <= '9')
operands.push(c - '0');
else if (c == 'x')
operands.push(replace);
else if (c == '(')
operators.push(c);
else if (c != ')') {
while(operators.size() > 0 && hasPrecedence(c, operators.top()))
evalOne(operands, operators);
operators.push(c);
}
else {
char op;
while((op = operators.top()) != '(')
evalOne(operands, operators);
operators.pop();
}
}
while(operators.size() > 0)
evalOne(operands, operators);
return operands.top();
}
public:
double SolveX(const string &expr) {
int equalPos = expr.find('=');
// assuming left = L(x)= ax + b, right = R(x) = cx + d
// x = (b - d) / (c - a)
// f(x) = L(x) - R(x)
// f(0) = b -d
// f(1) = (a-c) + (b-d)
// so x = f(0) / [f(1) -f(0)]
string left = expr.substr(0, equalPos);
string right = expr.substr(equalPos+1);
// Replace x with 0
int L0 = Eval(left, 0);
int R0 = Eval(right, 0);
// Replace x with 1
int L1 = Eval(left, 1);
int R1 = Eval(right, 1);
return (double)(L0 - R0)/(L1-R1 - L0 + R0);
}
};
int _tmain(int argc, _TCHAR* argv[])
{
int A[] = {1, 1};
vector vec(A, A+2);
Solution *s = new Solution();
double o = s->SolveX("4*x+3*(x-(4*x+x/3))=9");
Solution2 *s2 = new Solution2();
double o2 = s->SolveX("4*x+3*(x-(4*x+x/3))=9");
}
No comments:
Post a Comment