当第一眼看上去时，是懵的。

题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

本题中运算符仅包含 +-*/。保证对于 / 运算除数不为 0。特别地，其中 / 运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。

如：3*(5-2)+7 对应的后缀表达式为：3.5.2.-*7.+@。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。

输入输出样例

输入 #1

3.5.2.-*7.+@

输出 #1

16

输入 #2

10.28.30./*7.-@

输出 #2

-7

大家可以尝试有没有同感。

因为我们要找到是她在代码里如何运行，而不是具体的数学关系，不要紧盯她的数学定义。

要求明白后，不要一股脑实现她的全部功能。要从她最简单的样例下手。

一开始我的代码如下

#include <bits/stdc++.h>
using namespace std;


int stk[105];
int top ;
string s;


int main()
{
    cin>>s;
    int n=s.size();

    for(int i=0;i<n;i++)
    {
        if(s[i]!='.'&&s[i]!='+'&&s[i]!='-'&&s[i]!='*'&&s[i]!='/'&&s[i]!='@')
        {
            stk[top]=s[i]-'0';
            top++;
        }
        else if(s[i]=='+')
        {
            stk[top-2]=stk[top-2]+stk[top-1];
            top--;
        }
        else if(s[i]=='-')
        {
            stk[top-2]=stk[top-2]-stk[top-1];
            top--;
        }
        else if(s[i]=='*')
        {
            stk[top-2]=stk[top-2]*stk[top-1];
            top--;
        }
        else if(s[i]=='/')
        {
            stk[top-2]=stk[top-2]/stk[top-1];
            top--;
        }
        else if(s[i]=='@')
        {
            break;
        }
        else if(s[i]=='.')
        {
            continue;
        }
    }
    cout<<stk[top-1];
    return 0;
}

只能实现样例1.

再去想实现样例2，1的代码是一个你思维的支点，这样进可退，退可守。

改进后

#include <bits/stdc++.h>
using namespace std;


int stk[105];
int top ;
string s;
int num;
bool reading_num;

int main()
{
    cin>>s;
    int n=s.size();


    for(int i = 0; i < n; i++)
    {

        if(s[i] >= '0' && s[i] <= '9')
        {
            num = num * 10 + (s[i] - '0');
            reading_num = true;
        }
        else if(s[i] == '.')
        {
            if(reading_num)
            {
                stk[top++] = num;
                num = 0;
                reading_num = false;
            }
        }
        else if(s[i]=='+')
        {
            stk[top-2]=stk[top-2]+stk[top-1];
            top--;
        }
        else if(s[i]=='-')
        {
            stk[top-2]=stk[top-2]-stk[top-1];
            top--;
        }
        else if(s[i]=='*')
        {
            stk[top-2]=stk[top-2]*stk[top-1];
            top--;
        }
        else if(s[i]=='/')
        {
            stk[top-2]=stk[top-2]/stk[top-1];
            top--;
        }
        else if(s[i]=='@')
        {
            break;
        }

    }
    cout<<stk[top-1];
    return 0;
}

只是改进可以读取多位字符数字。

只有这一块。

for(int i = 0; i < n; i++)
    {

        if(s[i] >= '0' && s[i] <= '9')
        {
            num = num * 10 + (s[i] - '0');
            reading_num = true;
        }
        else if(s[i] == '.')
        {
            if(reading_num)
            {
                stk[top++] = num;
                num = 0;
                reading_num = false;
            }
        }

这样，才能真正地征服她，这道算法题。

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/dxy0706/article/details/157813575