题解 P1449 【后缀表达式】

没有输入 · 2019-07-22 15:03:36 · 题解

数据结构 · 栈

本题考查对数据结构·栈的认识。利用栈保存数字，在遇到运算符时取栈顶的两个元素进行运算后再放回栈顶即可。

读入方面，我没有做处理，而是放到后面，在运算的同时进行处理。

gets(a);

数据处理。乘10的幂，将字符转换为十进制数，放入栈内。

if(a[i]=='.')
{
    sum=0,k=1;
    for(int j=i-1;j>=0&&a[j]>='0'&&a[j]<='9';j--) sum=sum+(a[j]-48)*k,k*=10; 
    stk.push(sum);
    continue;
}

运算——遇到运算符时，取出栈顶元素进行运算。注意：由于栈先进后出的特点，做除法要用第二次取出的元素去除以第一次取出的元素。

sum=stk.top();
stk.pop(); 
if(a[i]=='+') sum=stk.top()+sum;
if(a[i]=='-') sum=stk.top()-sum;
if(a[i]=='*') sum=stk.top()*sum;
if(a[i]=='/') sum=stk.top()/sum;
stk.pop();
stk.push(sum);

最后输出即可。

总结

摸清栈先进后出的特性，利用这一特性即可方便的计算后缀表达式。字符转数字时要着重处理。处理的方法很多，这里就不一一列举了。

标程

#include<bits/stdc++.h>
using namespace std;
char a[1005];
int sum,k;
stack <int> stk;
int main()
{
    gets(a);
    for(int i=0;a[i]!='@';i++)
    {
        if(a[i]=='.')
        {
            sum=0,k=1;
            for(int j=i-1;j>=0&&a[j]>='0'&&a[j]<='9';j--) sum=sum+(a[j]-48)*k,k*=10; 
            stk.push(sum);
            continue;
        }
        if(a[i]>='0'&&a[i]<='9') continue;
        sum=stk.top();
        stk.pop(); 
        if(a[i]=='+') sum=stk.top()+sum;
        if(a[i]=='-') sum=stk.top()-sum;
        if(a[i]=='*') sum=stk.top()*sum;
        if(a[i]=='/') sum=stk.top()/sum;
        stk.pop();
        stk.push(sum);
    }
    printf("%d",stk.top());
    return 0;
}

我是没有输入，我们下次再见！