Online Judge Solutions

Wednesday, December 17, 2014

Solving Linear Equation with one variable

What would be the most efficient algorithm to solve a linear equation in one variable given as a string input to a function? For example, for input string:
"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