MOOC程式設計與算法練習題——遞歸#2694計算字首表達式

字首表達式的遞歸定義：

1. 一個數是一個逆波蘭表達式，值為該數
2. “運算符 逆波蘭表達式 逆波蘭表達式” 是逆波蘭表達式 ，值為兩個逆波蘭表達式的值運算的結果

遞歸法求字首表達式，代碼相當簡單。

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
double exp(){
	char s[20];
	cin >> s;
	switch(s[0]){
		case '+' : return exp()+exp();
		case '-' : return exp()-exp();
		case '*' : return exp()*exp();
		case '/' : return exp()/exp();
		default : return atof(s);
		break;
	}
}
int main(){
	printf("%f\n",exp());
	return 0;
}
           

還可以用棧從後往前用計算字尾表達式的方法計算字首表達式。

#include<iostream>
#include<stack>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm> 
using namespace std;
stack<double> num;
stack<string> expr;
string str;
double cal(double a,double b,char c){
	switch(c){
		case '+':
			return a + b;
		case '-':
			return a - b;
		case '*':
			return a * b;
		case '/':
			return a / b;
	}
}
int main(){
	while(cin >> str){
		expr.push(str);
	}
	while(!expr.empty()){
		str = expr.top();
		expr.pop();
		char c = str[0];
		if(c == '+' || c == '-' || c == '*' || c == '/'){
			double a = num.top();
			num.pop();
			double b = num.top();
			num.pop();
			num.push(cal(a,b,c));
		}
		else
			num.push(atof(str.c_str()));
	}
	printf("%f\n", num.top());
	return 0;
}
           

總之，計算字首/字尾表達式比求前/字尾表達式簡潔多了。