算法基礎：四則運算表達式--遞歸

題目：

輸入為四則運算表達式，僅由整數、+、－、*、/ 、(、) 組成，沒有空格，要求求其值。假設運算符結果都是整數。"/"結果也是整數。

輸入：(2+3)*(5+7)+9/3

輸出： 63

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
int factor_value();
int term_value();
int expression_value();
int main()
{
	cout<<expression_value()<<endl;
}
int expression_value()//求一個表達式的值
{
	int result=term_value();//求第一項的值
	bool more=true;
	while(more){
		char op=cin.peek();//看一個字元,不取走
		if(op=='+'||op=='-'){
			cin.get();//從輸入中取走一個字元
			int value=term_value();
			if(op=='+')result +=value;
			else result -=value;
		}
		else more=false;
	}
	return result;
}
int term_value()//求一個項的值
{
	int result=factor_value();//求第一個因子的值
	while(true){
		char op=cin.peek();
		if(op=='*'||op=='/'){
			cin.get();
			int value=factor_value();
			if(op=='*')
				result *=value;
			else
				result /=value;
		}
		else break;
	}
	return result;
}
int factor_value()//求一個因子的值
{
	int result=0;
	char c=cin.peek();
	if(c=='('){
		cin.get();
		result=expression_value();
		cin.get();
	}else{
		while(isdigit(c)){
			result=10*result+c-'0';
			cin.get();
			c=cin.peek();
		}
	}
	return result;
}
           

分析思路：

表達式是個遞歸的定義：

從以上就會得知最終傳回的終止條件就是整數，表達式也就是套娃的過程