M02694:波兰表达式 25-11-18

|递归|栈|

本题递归属于解析类递归：即输入具有特定的结构，需要按结构解析，属于一种较为特殊的递归类题目。本题的关键点有二：一、对不同的“字符”进行不同的return（基于相应的结构特点），二、运用全局变量pos进行定位，确保递归时每次读取的字符都是下一位。

#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>using namespace std;string s[110];
int pos = -1;double calculate(){pos+=1;if(s[pos]=="+"){return calculate()+calculate();}else if(s[pos]=="-"){return calculate()-calculate();}else if(s[pos]=="*"){return calculate()*calculate();}else if(s[pos]=="/"){return calculate()/calculate();}else{return stof(s[pos]);}
}int main(){int i=0;while(cin>>s[i]){i++;}double res = calculate();printf("%.6lf\n",res);return 0;
}