uva 533 - Equation Solver

Equation Solver

Write a program that can solve linear equations with one variable.

Input Specification 

The input file will contain a number of equations, each one on a separate line. All equations are strings of less than 100 characters which strictly adhere to the following grammar (given in EBNF):

    Equation   := Expression '=' Expression
    Expression := Term { ('+' | '-') Term }
    Term       := Factor { '*' Factor }
    Factor     := Number | 'x' | '(' Expression ')'
    Number     := Digit | Digit Number
    Digit      := '0' | '1' | ... | '9'

Although the grammar would allow to construct non-linear equations like ``x*x=25", we guarantee that all equations occuring in the input file will be linear in x. We further guarantee that all sub-expressions of an equation will be linear in xtoo. That means, there won't be test cases like

x*x-x*x+x=0

which is a linear equation but contains non-linear sub-expressions (x*x).
Note that all numbers occuring in the input are non-negative integers, while the solution for x is a real number.

Output Specification 

For each test case, print a line saying ``Equation #i (where i is the number of the test case) and a line with one of the following answers:

• If the equation has no solution, print ``No solution.".
• If the equation has infinitely many solutions, print ``Infinitely many solutions.".
• If the equation has exactly one solution, print ``x = solution" where solution is replaced by the appropriate real number (printed to six decimals).

Print a blank line after each test case, but the last one.

Sample Input 

x+x+x=10
4*x+2=19
3*x=3*x+1+2+3
(42-6*7)*x=2*5-10

Sample Output 

Equation #1
x = 3.333333

Equation #2
x = 4.250000

Equation #3
No solution.

Equation #4
Infinitely many solutions.

BNF calculation 先乘除後加減

#include<stdio.h>
#include<vector>
#include<string>
#include<cstring>
#include<stack>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

struct Equa{
    Equa(){cons=xfac=0;}
    Equa(int a,int b):cons(a),xfac(b){}
    Equa operator *(const Equa &b){
        Equa a;
        a.cons=cons*b.cons;
        a.xfac=cons*b.xfac+xfac*b.cons;
        return a;
    }
    Equa operator +(const Equa &b){
        Equa a;
        a.cons=cons+b.cons;
        a.xfac=b.xfac+xfac;
        return a;
    }
    Equa operator -(const Equa &b){
        Equa a;
        a.cons=cons-b.cons;
        a.xfac=xfac-b.xfac;
        return a;
    }
    int cons,xfac;
};
stack<Equa>fcs;
stack<char>ope;
int cases=1;
char chs[105];
Equa getNum(int pos,int &i){
    int c=0;
    while(isdigit(chs[pos]))c=c*10+chs[pos]-'0',pos++;
    i=pos;
    if(DBG)printf("getnum %d\n",c);
    return Equa(c,0);
}
Equa cal(char oc){
    Equa cea=fcs.top(),ea;fcs.pop();
    char co;
    if(DBG)printf("cal %c\n",oc);
    if(oc==')'){                     //clear all
        while(ope.size()&&ope.top()!='('){
            co=ope.top(),ope.pop();
            ea=fcs.top(),fcs.pop();
            if(co=='-')cea=ea-cea;
            if(co=='+')cea=ea+cea;
            if(co=='*')cea=ea*cea;
        }
        ope.pop();
    }
    if(oc=='-'||oc=='+')  {          //cal *
        while(ope.size()&&ope.top()=='*'){
            ope.pop();
            ea=fcs.top(),fcs.pop();
            //if(DBG)printf("a b (%d %d)(%d %d)\n",cea.cons,cea.xfac,ea.cons,ea.xfac);
            cea=ea*cea;
        }
    }
    if(DBG)printf("cal: (%d %d)\n",cea.cons,cea.xfac);
    return cea;
}
Equa getExp(int start,int end){
    char co;
    Equa ea,cea;
    ope.push('(');
    REP(i,start,end+1){
        if(isdigit(chs[i]))ea=getNum(i,i),fcs.push(ea);
        if(chs[i]=='x')fcs.push(Equa(0,1));
        if(chs[i]=='*'||chs[i]=='(')ope.push(chs[i]);
        if(chs[i]=='-'||chs[i]=='+')cea=cal(chs[i]),fcs.push(cea),ope.push(chs[i]);
        if(chs[i]==')')cea=cal(')'),fcs.push(cea);
        if(chs[i]=='='||chs[i]=='\0')cea=cal(')');
    }
    if(DBG){if(ope.size())printf("ope size %d\n",ope.size());
        if(fcs.size())printf("fcs size %d\n",fcs.size());
    }
    return cea;
}
void ans(){
    int len=strlen(chs);
    Equa a,b;
    rep(i,strlen(chs))if(chs[i]=='='){a=getExp(0,i),b=getExp(i+1,len);break;}
    //solve
    int xc=a.xfac-b.xfac,cc=b.cons-a.cons;
    //if(DBG)printf("xc cc %d %d\n",xc,cc);
    printf("Equation #%d\n",cases++);
    if(xc==0&&cc!=0)printf("No solution.\n");
    else if(xc==0&&cc==0)printf("Infinitely many solutions.\n");
    else printf("x = %.6f\n",(double)cc/xc);
}
int main(){
    bool ll=0;
    while(scanf("%s",chs)==1){
        if(ll)printf("\n");ll=1;
        ans();
    }
}