[递归] 四则运算表达式的值

四则运算表达式的值

题目描述

输入一个包括+、-、*、/和()的四则运算表达式，你能算出表达式的值吗？
这个表达式满足：
1、没有括号不匹配的情况，但可能有嵌套的情形
2、操作数均为整数，但需考虑正负数
3、没有非法表达式，也没有零作除数的情况
4、所有操作都可以视为整型计算，不考虑分数和小数的情况
5、中间结果和最终结果不会超出int的表示范围

关于输入

若干行，每行为一个合法的四则运算表达式

关于输出

若干行，为对应的运算结果

例子输入

1+3+5
5*(3+7)
-(-4/(1+3))*5-1*2*3
+2+3+5

例子输出

9
50
-1
10

解题分析

?由于加减乘除具有不同的优先级，所以对于一个式子我们应该拆分去看。考虑表达式具有显著的递归性质，于是考虑用函数递归调用方法取解决本问题。基本思路是，定义一个函数f(i,j)为计算下标从i到j的式子的值。然后根据优先级 (数字本身)>(括号)>(乘除)>(加减)去定义函数f(i,j)的计算过程。需要注意的点是: 从后往前进行计算；对于不合法的位置，一律返回0；如果在前面发现了括号，直接跳过，因为它的优先级极其高；学会用数数法去寻找匹配的括号的位置。

程序是一个用于计算四则运算表达式的值的程序。通过递归和栈的思想来解析表达式，并按照运算符的优先级进行计算。

程序的主要思路是：

1. 定义一个函数matchBracket，用于匹配括号。它从右向左遍历表达式，当遇到右括号时，计数器加1，遇到左括号时，计数器减1，直到计数器为0，找到与当前右括号匹配的左括号的位置。
2. 定义一个函数calculate，用于计算表达式的值。它从右向左遍历表达式，首先处理括号内的表达式。如果遇到括号，则调用matchBracket函数找到与当前右括号匹配的左括号的位置，并递归调用calculate函数计算括号内的表达式的值。
3. 在处理括号之后，继续从右向左遍历表达式，按照运算符的优先级进行计算。首先处理加法和减法，如果遇到加号，则将左右两侧的表达式的值相加；如果遇到减号，则将左侧表达式的值减去右侧表达式的值。然后处理乘法和除法，如果遇到乘号，则将左右两侧的表达式的值相乘；如果遇到除号，则将左侧表达式的值除以右侧表达式的值。
4. 最后，如果表达式中只有一个数字，则直接返回该数字的值。
5. 在主函数中，通过循环读取输入的表达式，并调用calculate函数计算表达式的值，并输出结果。

这个程序的算法基于递归和栈的思想，通过不断缩小问题规模，将复杂的四则运算表达式转化为简单的加减乘除运算，最终得到结果。程序还考虑了括号的嵌套和运算符的优先级，能够正确计算包含括号和多个运算符的表达式。

代码实现

#include <iostream>
#include <cmath>
#include <cstring>
#define MAXLEN 10000
using namespace std;

char formulation[MAXLEN];
int result;

int matchBracket(int left,int right){
	int count=1;
	for(int i=right;i>=left;i--){
		if(formulation[i]==')'){
			count++;
		}
		else if(formulation[i]=='('){
			count--;
		}
		if(count==0){
			return i;
		}
	}
	return 0;
}

int calculate(int left,int right){
	for(int i=right;i>=left;i--){
		if(formulation[i]==')'){
			i=matchBracket(left,i-1);
		}
		else if(formulation[i]=='+'){
			return calculate(left,i-1)+calculate(i+1,right);
		}
		else if(formulation[i]=='-'){
			return calculate(left,i-1)-calculate(i+1,right);
		}
	}
	for(int i=right;i>=left;i--){
		if(formulation[i]==')'){
			i=matchBracket(left,i-1);
		}
		else if(formulation[i]=='*'){
			return calculate(left,i-1)*calculate(i+1,right);
		}
		else if(formulation[i]=='/'){
			return calculate(left,i-1)/calculate(i+1,right);
		}
	}
	if(formulation[right]==')' && formulation[left]=='('){
		return calculate(left+1,right-1);
	}
	if(formulation[right]>='0' && formulation[right]<='9'){
		int ans=0;
		for(int i=right,j=0;i>=left;i--,j++){
			ans+=pow(10,(double)j)*(formulation[i]-'0');
		}
		return ans;
	}
	return 0;
}

int main(){
	while(cin.getline(formulation,MAXLEN)){
		result=calculate(0,strlen(formulation)-1);
		cout<<result<<endl;
	}
	return 0;
}