题解 P1449 【后缀表达式】

Imakf · 2017-12-28 18:35:29 · 题解

题目分析

题目让我们读入后缀表达式，计算最后的答案，无视负数、小数、long long肯定不会爆

我们采用一种用数组模拟栈的方法

读入

char op;
int now=0;
while((op=getchar())!='@'){
    if(op>='0'&&op<='9') now*=10,now+=op-'0';
    else if(op=='.'){
        stk[++i]=now;
        now=0;
        }
}

这是本蒟蒻的读入代码，读取数字，类似于手写的快读 比如读入12345

step1 0-->0-->1

step2 1-->10-->12

step3 12-->120-->123

step4 123-->1230-->1234

step5 1234-->12340-->12345

一旦读取的不是数字就把这个数字压入模拟栈

运算

        else if(op=='+'){
            stk[i-1]=stk[i-1]+stk[i];
            stk[i]=0;
            i--;
        }
        else if(op=='-'){
            stk[i-1]=stk[i-1]-stk[i];
            stk[i]=0;
            i--;
        }
        else if(op=='*'){
            stk[i-1]=stk[i-1]*stk[i];
            stk[i]=0;
            i--;
        }
        else if(op=='/'){
            stk[i-1]=stk[i-1]/stk[i];
            stk[i]=0;
            i--;
        }

读到运算符就把栈顶上两个数做运算（做减法时减数和被减数要正确） 然后弹出栈顶两个元素 再将结果压入栈顶

AC代码

    #include<iostream>
    #include<cstdio>
    using namespace std;
    long long stk[1000];
    int main(){
    long long i=0,now=0;
    char op;
    while((op=getchar())!='@'){
        if(op>='0'&&op<='9') now*=10,now+=op-'0';
        else if(op=='.'){
            stk[++i]=now;
            now=0;
        }
        else if(op=='+'){
            stk[i-1]=stk[i-1]+stk[i];
            stk[i]=0;
            i--;
        }
        else if(op=='-'){
            stk[i-1]=stk[i-1]-stk[i];
            stk[i]=0;
            i--;
        }
        else if(op=='*'){
            stk[i-1]=stk[i-1]*stk[i];
            stk[i]=0;
            i--;
        }
        else if(op=='/'){
            stk[i-1]=stk[i-1]/stk[i];
            stk[i]=0;
            i--;
        }
    }
    cout<<stk[1];
    return 0;
}