关于如何做算法题的一些感悟 以P1449 后缀表达式为例

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

题目描述

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

本题中运算符仅包含 +-*/。保证对于 / 运算除数不为 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;
}
}

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