题解 P1449 【后缀表达式】

· · 题解

此题是一道使用栈（stack）的裸题。。。

思路根P1981表达式求值非常像。

重点：此题由于采用后缀表达方式，所以在读到运算符号时可以无条件运算，无需考虑优先级，比P1981简单！！！（也就是说不用符号栈）

思路：先将整个表达式一起读入，接下来：

  1. 如果碰到数字，将其放入临时数组当中，方便以后求数字
  2. 如果碰到'.'，那么将临时数组中的字符串转化成数字（具体操作看程序注释），将其压入数字栈中
  3. 如果碰到运算符号，那么将栈顶的两个元素取出做相应的运算（注意：如果碰到-'或'/'应该用栈顶第二个元素减或除以栈顶元素！！！）
  4. 最后输出数字栈中剩余的最后一个元素即可

模拟（想抄代码的童鞋们可以跳过此部分）：

输入：3.18.56.+*@

碰到数字3，放入临时数组中：

      stack    ccty：3|*|*|*|*|*|*|
栈顶->  空 
栈底->  空      read:3

接下来发现'.'，转化数字压入数字栈中：

      stack    ccty：*|*|*|*|*|*|*|*
栈顶->   
栈底->  3      read:.

接下来碰到1，放入临时数组中：

      stack    ccty：1|*|*|*|*|*|*|*
栈顶->   
栈底->  3      read:1

接下来快速模拟：

      stack    ccty：1|8|*|*|*|*|*|*
栈顶->  18 
栈底->  3      read:8
      stack    ccty：5|*|*|*|*|*|*|*
栈顶->  18 
栈底->  3      read:5
      stack    ccty：5|6|*|*|*|*|*|*
栈顶->  56
       18
栈底->  3      read:6

接下来读入加号。
将数字栈栈顶两个元素相加并将和压回数字栈中：

      stack    ccty：*|*|*|*|*|*|*|*
栈顶->  74     18+56=74
栈底->  3      read:+

同理：

      stack    ccty：*|*|*|*|*|*|*|*
栈顶->         74*3=222  
栈底->  222    read:*

故最后答案等于222（好不吉利的数字）。

接下来请看代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<cstring>
#define is ==//装b
#define isnot !=
using namespace std;
stack<int>num;//数字栈
int Num;
char Ch;
int num2;
char str[10001];//表达式
char ccty[21];//临时数组
int flag=0,i;//flag用来判断数字是否已读尽
int numa,numb;
int Makenum(){//将临时数组中的字符转化成数字的函数
    int ret=0;
    for(int i=0;i<=strlen(ccty)-1;++i){
        if(ccty[i]=='*')break;
        ret=ret*10+ccty[i]-'0';
        ccty[i]='*';//边转化边清空，省时间
    }
    return ret;//返回转化后的值
}
int main()
{
    cin>>str;//读入整个表达式
    char cha;//当前碰到的字符
    cha=str[0];
    int k=0;
    while(cha!='@'){//如果未发现结束符号，那么运行
        if(flag==0)i=0;
        if(cha>='0'&&cha<='9'){//如果是数字
            flag=1;
            ccty[i]=cha;//将它塞入临时数组中
            i++;
        }
        if(cha is '.'){//自己看上边的装b定义 
            flag=0;//数已读尽
            Num=Makenum();//转化成数字
            num.push(Num);//压入栈中
        }
        if((cha<'0'||cha>'9')&&cha isnot '.'){//装b*2
            numa=num.top();
            num.pop();
            numb=num.top();
            num.pop();//取出栈顶前两个数字
            if(cha=='+')num.push(numb+numa);//加和乘反不反无所谓
            if(cha=='-')num.push(numb-numa);//减和除就一定要反过来了
            if(cha=='*')num.push(numb*numa);
            if(cha=='/')num.push(numb/numa);
        }
        k++;
        cha=str[k];//读取下一个字符
    }
    cout<<num.top();//输出答案
}

题外话：这里是栈（stack）的class类代码（不想用STL的童鞋们可以参考）：

/*说明：stk.push(n)表面上是将n压入stk中，实际上是将n
压入stk中包含的a数组内*/
template<typename T>class stack{
    T a[100001];
    int tail;
    public:
        void push(T n){//压入数据
            a[tail++]=n;
        }
        void pop(){//弹出栈顶元素
            tail--;
        }
        T top(){//返回栈顶元素
            return a[tail-1];
        }
        int size(){//返回栈内元素的个数
            return tail;
        }
        bool empty(){//判断栈是否为空
            return tail==0;
        }
};
用法：
stack<元素基类型> 类名;
如：
stack<char> stk//建立一个存储字符的名为stk的栈
stack<int> num//建立一个存储int整型的名为num的栈
stack<double> dou//同上