NYOJ 267 郁闷的C小加（二）（字符串处理）

描述

聪明的你帮助C小加解决了中缀表达式到后缀表达式的转换（详情请参考“郁闷的C小加（一）”），C小加很高兴。但C小加是个爱思考的人，他又想通过这种方法计算一个表达式的值。即先把表达式转换为后缀表达式，再求值。这时又要考虑操作数是小数和多位数的情况。

输入

第一行输入一个整数T，共有T组测试数据（T<10)。每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数并且小于1000000。数据保证除数不会为0。
输出

对于每组测试数据输出结果包括两行，先输出转换后的后缀表达式，再输出计算结果，结果保留两位小数。两组测试数据之间用一个空行隔开。
样例输入

2

1+2=

(19+21)*3-4/5=
样例输出

12+=

3.00
```
1921+3*45/-=

119.20
```

分析：

典型的表达式求值，数据结构书上也有详细的关于表达式求值的介绍，对于一个中缀形式表达式，我们没有办法直接对它进行计算，首先得把它转换为后缀形式，然后利用后缀形式来计算表达式的值。

代码：

#include<string>

#include<iostream>

#include<algorithm>

#include<stdio.h>

#include<string.h>

#include<stack>

using namespace std;

char a[1009],b[1009];

char pri[300];

void trans(char a[])///中缀转后缀

{

    stack<char>q;///栈用来存储操作数

    q.push('=');///用'='压栈，是为了与后来的操作符比较的时候，他的优先级最低

    int j=0;

    for(int i=0; a[i]!='='; i++)

    {

        if(a[i]>='0'&&a[i]<='9'||a[i]=='.')///可能有小数

            b[j++]=a[i];

        else

        {

            b[j++]='#';///将连着的多个操作数分隔开

            if(a[i]=='(')

                q.push(a[i]);

            else if(a[i]==')')///一直出栈到'('

            {

                while(q.top()!='(')

                {

                    b[j++]=q.top();

                    q.pop();

                }

                q.pop();

            }

            else

            {

                while(pri[a[i]]<=pri[q.top()])

                {

                    b[j++]=q.top();

                    q.pop();

                }

                q.push(a[i]);

            }

        }

    }

    while(q.top()!='=')

    {

        b[j++]=q.top();

        q.pop();

    }

    b[j++]='=';

    b[j]='\0';

}

double JiSuan(char b[])

{

    //puts(b);

    char c[100];

    int j=0;

    stack<double>st;

    for(int i=0; b[i]!='='; i++)

    {

        if(b[i]>='0'&&b[i]<='9'||b[i]=='.')

            c[j++]=b[i];

        else

        {

            if(j!=0)

            {

                st.push(atof(c));///自动将字符转换为double

              //  cout<<"c  "<<st.top()<<endl;

                memset(c,'\0',sizeof(c));

                j=0;

            }

            if(b[i]!='#')

            {

                double n1;

                double n2;

                double n3;

                switch(b[i])

                {

                case '+':

                    n1=st.top();

                    st.pop();

                    n2=st.top();

                    st.pop();

                    n3=n2+n1;

                    st.push(n3);

                    break;

                case '-':

                    n1=st.top();

                    st.pop();

                    n2=st.top();

                    st.pop();

                    n3=n2-n1;

                    st.push(n3);

                     break;

                case '*':

                    n1=st.top();

                    st.pop();

                    n2=st.top();

                    st.pop();

                    n3=n2*n1;

                    st.push(n3);

                     break;

                case '/':

                    n1=st.top();

                    st.pop();

                    n2=st.top();

                    st.pop();

                    n3=n2/n1;

                    st.push(n3);

                     break;

                }

            }

        }

    }

    return st.top();

}

int main()

{

    int T;

    pri['=']=-1;

    pri['(']=0;

    pri['+']=1;

    pri['-']=1;

    pri['*']=2;

    pri['/']=2;

    pri[')']=3;

    scanf("%d",&T);

   for(int k=1;k<=T;k++)

    {

        if(k!=1)

        printf("\n");///测试数据的问题，加不加换行都能过

        memset(a,'\0',sizeof(a));

        memset(b,'\0',sizeof(b));

        scanf(" %s",a);

        // puts(a);

        trans(a);

        for(int i=0; b[i]!='\0'; i++)

        {

            if(b[i]!='#')

                printf("%c",b[i]);

        }

        printf("\n");

        printf("%.2lf\n",JiSuan(b));

    }

    return 0;

}

巴特西

NYOJ 267 郁闷的C小加（二）（字符串处理）

最新文章

热门文章

巴特西

NYOJ 267 郁闷的C小加（二） （字符串处理）

最新文章

热门文章

NYOJ 267 郁闷的C小加（二）（字符串处理）