表达式计算

题目概要： 给一个算数表达式，包涵加减乘除乘方几种运算，和小括号（可能会出现多余的情况），计算结果

看别人写的题解都很详细，但是每一份题解都给的是，怎么分，但是没有告诉为什么这么分。

我们知道递归可以把一个大问题，分化为几个小问题，那么在这道题什么时候要分化呢？？

  1. 遇到括号，我们知道括号要单独计算括号里的表达式
  2. 遇到运算符，我们知道遇到运算符要把左右两边进行相应的运算

那么他们之间的顺序呢？？

  1. 运算符之间：先递归优先级小的，再递归优先级大的（相同运算符，后出现的优先级小，因为我们是从左往右计算）

比如 +

先递归+，可以把问题分化为和

  1. 出现括号，把括号即里面的运算表达式看成一个数

我们知道，数在递归过程会被忽略，直到递归到区间内只剩数值，返回答案

那把括号即里面的运算表达式看成一个数同理，在递归过程会被忽略，直到剩下这个括号及里面的运算表达式，再计算这个括号，返回答案

for (int i = l;i <= r;i++){
		if (s[i] == ')') cnt--;
		if (s[i] == '(') cnt++;
		if ((s[i] == '+'||s[i] == '-')&&cnt == 0) add = i;
		if ((s[i] == '*'||s[i] == '/')&&cnt == 0) mul = i;
		if (s[i] == '^'&&cnt == 0) power = i;
	}

首先看这段代码会产生一些问题

Q: 这份代码的目的是什么？

A: 找到最小优先级的运算符进行递归

Q: cnt是怎么运行的？

A:

  • 假设没有多余的括号,cnt == 0

  1. xxxxx ：只有数，直接返回答案

  2. (xxxx): 转化成第一种情况

  3. (xx)+(xx): 会拆分成(xx)+(xx) （同前两种情况）

  4. xxx+(xxx)+xxx:中间有括号，会拆分成xxx和(xxx)和xxx进行递归 （同前三种情况）

	if (cnt == 0){
		if (s[l] == '('&&add + mul + power == 0) return dfs(l+1,r-1);
		if (add){
			if (s[add] == '+') return dfs(l,add-1) + dfs(add+1,r);
			if (s[add] == '-') return dfs(l,add-1) - dfs(add+1,r);
		}
		if (mul){
			if (s[mul] == '*') return dfs(l,mul-1) * dfs(mul+1,r);
			if (s[mul] == '/') return dfs(l,mul-1) / dfs(mul+1,r);
		}
		if (power) return pow(dfs(l,power-1),dfs(power+1,r));
		int res = 0;
		for (int i = l;i <= r;i++) res = res*10+s[i]-'0';
		return res;
	}
  • 那有多余的左括号呢？？ cnt > 0

  1. ((xxxx)+xxx ：按照样例脑算一下，没有最小的运算符，所以需要我们手动清除多余括号，再进行匹配

  2. xx+((xxx)xxx ：会分解为xx (同括号匹配的情况) 和((xxxx)+xxx (同第一种情况)

if (cnt > 0){
		if (s[l] == '(') return dfs(l+1,r);
		if (add){
			if (s[add] == '+') return dfs(l,add-1) + dfs(add+1,r);
			if (s[add] == '-') return dfs(l,add-1) - dfs(add+1,r);
		}
		if (mul){
			if (s[mul] == '*') return dfs(l,mul-1) * dfs(mul+1,r);
			if (s[mul] == '/') return dfs(l,mul-1) / dfs(mul+1,r);
		}
		if (power) return pow(dfs(l,power-1),dfs(power+1,r));
	}
  • 右括号同理

所以整体的代码为

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int maxn = 1e5+10;
#define int long long
char s[maxn];
int dfs(int l,int r){
	int add = 0,mul = 0,power = 0,cnt = 0;
	for (int i = l;i <= r;i++){
		if (s[i] == ')') cnt--;
		if (s[i] == '(') cnt++;
		if ((s[i] == '+'||s[i] == '-')&&cnt == 0) add = i;
		if ((s[i] == '*'||s[i] == '/')&&cnt == 0) mul = i;
		if (s[i] == '^'&&cnt == 0) power = i;
	}
	if (cnt == 0){
		if (s[l] == '('&&add + mul + power == 0) return dfs(l+1,r-1);
		if (add){
			if (s[add] == '+') return dfs(l,add-1) + dfs(add+1,r);
			if (s[add] == '-') return dfs(l,add-1) - dfs(add+1,r);
		}
		if (mul){
			if (s[mul] == '*') return dfs(l,mul-1) * dfs(mul+1,r);
			if (s[mul] == '/') return dfs(l,mul-1) / dfs(mul+1,r);
		}
		if (power) return pow(dfs(l,power-1),dfs(power+1,r));
		int res = 0;
		for (int i = l;i <= r;i++) res = res*10+s[i]-'0';
		return res;
	}
	if (cnt > 0){
		if (s[l] == '(') return dfs(l+1,r);
		if (add){
			if (s[add] == '+') return dfs(l,add-1) + dfs(add+1,r);
			if (s[add] == '-') return dfs(l,add-1) - dfs(add+1,r);
		}
		if (mul){
			if (s[mul] == '*') return dfs(l,mul-1) * dfs(mul+1,r);
			if (s[mul] == '/') return dfs(l,mul-1) / dfs(mul+1,r);
		}
		if (power) return pow(dfs(l,power-1),dfs(power+1,r));
	}
	if (cnt < 0){
		if (s[l] == '(') return dfs(l,r-1);
		if (add){
			if (s[add] == '+') return dfs(l,add-1) + dfs(add+1,r);
			if (s[add] == '-') return dfs(l,add-1) - dfs(add+1,r);
		}
		if (mul){
			if (s[mul] == '*') return dfs(l,mul-1) * dfs(mul+1,r);
			if (s[mul] == '/') return dfs(l,mul-1) / dfs(mul+1,r);
		}
		if (power) return pow(dfs(l,power-1),dfs(power+1,r));
	}
}
signed main(){
	scanf ("%s",s+1);
	int len = strlen(s+1);
	printf("%lld\n",dfs(1,len));
	return 0;
}