NYOJ:35-表达式求值

表达式求值

时间限制：3000 ms | 内存限制：65535 KB
难度：4

描述
ACM队的mdd想做一个计算器，但是，他要做的不仅仅是一计算一个A+B的计算器，他想实现随便输入一个表达式都能求出它的值的计算器，现在请你帮助他来实现这个计算器吧。
比如输入：“1+2/4=”，程序就输出1.50（结果保留两位小数）
输入
第一行输入一个整数n，共有n组测试数据（n<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。
数据保证除数不会为0
输出
每组都输出该组运算式的运算结果，输出结果保留两位小数。
样例输入
2
1.000+2/4=
((1+2)*5+1)/4=
样例输出
1.50
4.00

此题比较有代表性，搞清楚符号的优先级

代码:

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

#define STACK_INIT_SIZE 1024
#define STACKIN_INCREMENT 30

char Precede_Matrix[7][7]=
{
    {'>', '>', '<', '<', '<', '>', '>',},
    {'>', '>', '<', '<', '<', '>', '>',},
    {'>', '>', '>', '>', '<', '>', '>',},
    {'>', '>', '>', '>', '<', '>', '>',},
    {'<', '<', '<', '<', '<', '=', '0',},
    {'>', '>', '>', '>', '0', '>', '>',},
    {'<', '<', '<', '<', '<', '0', '=',}
};

char Precede(char a,char b)
{
    int i=0,j=0;
    switch(a)
    {
    case '+' :
        i = 0;
        break;
    case '-' :
        i = 1;
        break;
    case '*' :
        i = 2;
        break;
    case '/' :
        i = 3;
        break;
    case '(' :
        i = 4;
        break;
    case ')' :
        i = 5;
        break;
    case '#' :
        i = 6;
        break;
    default :
        cout << "Error1!" << endl;
    }
    switch(b)
    {
    case '+' :
        j = 0;
        break;
    case '-' :
        j = 1;
        break;
    case '*' :
        j = 2;
        break;
    case '/' :
        j = 3;
        break;
    case '(' :
        j = 4;
        break;
    case ')' :
        j = 5;
        break;
    case '#' :
        j = 6;
        break;
    default :
        cout << "Error1!" << endl;
    }
    return Precede_Matrix[i][j];
}

double Operate(double a,char oper,double b)
{
    switch(oper)
    {
    case '+':
        return a + b;
    case '-':
        return a- b;
    case '*':
        return a* b;
    case '/':
        return a / b;
    default:
        cout << "Error3!" << endl;
        return -1;
    }
}

struct stack_char
{
    char *base;
    char *top;
    int stacksize;
};

struct stack_double
{
    double *base;
    double *top;
    int stacksize;
};

template <class T2,class T1>//类模板
void InitStack(T1 &S)
{
    S.base=(T2*)malloc(STACK_INIT_SIZE*sizeof(T2));
    if(!S.base)
        cout<<"Overflow2!"<<endl;
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
}

template <class T2,class T1>
void Push(T1 &S,T2 e)
{
    if(S.top-S.base>=S.stacksize)
    {
        S.base=(T2*)realloc(S.base,(S.stacksize+STACKIN_INCREMENT)*sizeof(T2));
        if(!S.base)
            cout<<"Overflow3!"<<endl;
        S.top=S.base+S.stacksize;
        S.stacksize += STACKIN_INCREMENT;
    }
    *S.top++=e;
}

template <class T2,class T1>
void Pop(T1 &S,T2 &e)
{
    if(S.top==S.base)
        cout << "Stack is empty!!" << endl;
    e=*--S.top;
}

template <class T2,class T1>
T2 GetTop(T1 S)
{
    if(S.top==S.base)
        cout << "Stack is empty!!" << endl;
    return  *--S.top;
}

bool IsOperand(char c)
{
    if(('0'<=c&&c<='9')||c=='.')
        return true;
    else
        return false;
}

int main()
{
    string str;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>str;
        str[str.length()-1]='#';
        // str.push_back('#');// 最后是#（结束标志）
        double a,b;
        char x;
        char theta;
        stack_char OPTR;
        InitStack<char>(OPTR);
        Push(OPTR,'#');
        stack_double OPND;
        InitStack<double> (OPND);
        int i=0;
        char c=str[i++];//

        double operand=0;

        while(!(c=='#'&&GetTop<char>(OPTR)=='#'))
        {
            if(IsOperand(c))
            {
                operand=atof(&str[i-1]); //把从c开头的数转化成double
                Push(OPND,operand);
                while(IsOperand(str[i]))
                    i++;
                c=str[i++];

            }
            else
            {
                switch(Precede (GetTop<char> (OPTR), c))
                {

                case '<':
                    Push(OPTR,c);
                    c=str[i++];
                    break;

                case '=':
                    Pop(OPTR,x);
                    c=str[i++];
                    break;
                case '>':
                    Pop(OPTR,theta);
                    Pop(OPND,b);
                    Pop(OPND,a);
                    Push(OPND,Operate(a, theta, b));
                    break;
                default:
                    cout<<"operator Error!"<<endl;
                    break;
                }
            }
        }
        printf("%0.2lf\n",GetTop<double>(OPND));
        //cout<<GetTop<double>(OPND)<<endl;

        free(OPTR.base);
        free(OPND.base);
    }
    return 0;
}