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

发布时间:2023年12月29日

四则运算表达式的值

题目描述

输入一个包括+、-、*、/和()的四则运算表达式,你能算出表达式的值吗?
这个表达式满足:
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;
}

文章来源:https://blog.csdn.net/StudyingPanda/article/details/135282841
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。