表达式求值

表达式求值

typedef double type;

int idx;
stack<type>Sn;
type num[__];

struct Operator
{
    //定义符号
    static bool is(char c)
    {
        return c=='+' || c=='-' || c=='*'
            || c=='/' || c=='(' || c==')';
    }

    char o;
    Operator() {}

    void operator=(const char c){o=c;}

    bool operator==(const char c){return o==c;}

    //定义符号优先级
    bool operator<=(const Operator &b)const
    {
        if(o=='*' || o=='/')
            return b.o=='*' || b.o=='/';
        if(o=='+' || o=='-')
            return b.o!='(';
        if(o==')')return true;
        return false;
    }

    //定义符号运算
    type fun()
    {
        type x=Sn.top();Sn.pop();
        type y=Sn.top();Sn.pop();
        if(o=='+')return y+x;
        if(o=='-')return y-x;
        if(o=='*')return y*x;
        if(o=='/')return y/x;
    }
}op[__];

stack<Operator>So;

//读浮点数
int read_num(int x)
{
    ll fz=0,fm=0;
    for(;;++x)
    {
        if(fm)fm*=10;
        if(a[x]=='.')fm=1;
        else fz=fz*10+(a[x]-'0');
        if(!a[x+1] || Operator::is(a[x+1]))
            break;
    }
    if(!fm)fm=1;
    num[++idx]=fz*1.0/fm;
    return x;
}

void compare(Operator c)
{
    while(!So.empty() && c<=So.top())
    {
        if(So.top()=='('){So.pop();return;}
        Sn.push(So.top().fun()),So.pop();
    }
    So.push(c);
}

type calculate()
{
    for(int i=1;i<=idx;++i)
        if(op[i]==0)Sn.push(num[i]);
        else compare(op[i]);
    for(;!So.empty();So.pop())
        Sn.push(So.top().fun());
    type res=Sn.top();Sn.pop();
    return res;
}

int main()
{
    sf("%s",a+1);
    int n=strlen(a+1);

    for(int i=1;i<=n;++i)
    {
        if(Operator::is(a[i]))
            op[++idx]=a[i];
        else i=read_num(i),op[idx]=0;
    }
    pf("%.2f\n",calculate());
    return 0;
}