【模拟 + 栈】AcWing 151. 表达式计算4

这题括号多余的情况好恶心 orz，以及负数的情况也增加了这题的难度。

分析

首先，解决一般的中缀表达式转后缀表达式问题：

这里的运算符包括 +,-,*,/,^，当然，扩大运算符包含的集合的时候我们也可以类似推广。

考虑用一个答案栈 res 以及运算符栈 ops 来操作。

遇到数字的时候，将它丢入 res。
遇到左括号的时候，将它丢入 ops。
遇到右括号的时候，开始对 ops 执行出栈操作直到遇到左括号。
遇到运算符的时候，只要 ops 栈顶的运算符优先级高于当前运算符，就一直对 ops 执行出栈操作。

这样我们就可以将中缀转后缀了。

下面对后缀表达式求值：
考虑用一个栈维护，
遍历后缀表达式，当遇到数的时候就丢入栈；否则遇到的是运算符，此时我们将栈顶两个数拿出来用这个运算符进行运算再将结果丢入栈中。

遍历完后缀表达式后栈只剩一个数，这就是答案。

至此，原理讲述完毕。

但这题很毒瘤，会有括号多余的情况以及负数的情况。

接下来的操作由为本人乱搞得出，如果找到 hack 数据可以发给我 qwq~，但目前我试了许多奇怪的数据都可以过。

对于括号多余的情况，考虑对原序列 s 进行一遍类似于括号匹配的操作：维护两个变量 cntL, cntR，见代码：

int cntL=0, cntR=0;
for(auto i: s){
	if(i=='(') cntL++;
	else if(i==')' && cntL) cntL--;
	else if(i==')' && !cntL) cntR++;
}

然后对于负数的情况，例如 -1+3，将 -1 替换为 (0-1)*。

实现

// Problem: 表达式计算4
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/153/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()

#define int long long

using pii = pair<int, int>;
using ll = long long;

inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

map<char, int> mp;

string c2str(char ch){
	string s; s+=ch;
	return s;
}

vector<string> get(string s){
	vector<string> res;
	stack<char> ops;
	
	rep(j,0,s.size()-1){
		char i=s[j];
		if(isdigit(i)){
			string num;
			while(j<s.size() && isdigit(s[j])){
				num+=s[j];
				j++;
			}
			res.pb(num);
			j--;
		}
		else if(i=='(') ops.push('(');
		else if(i==')'){
			while(ops.top()!='('){
				res.pb(c2str(ops.top()));
				ops.pop();
			};
			ops.pop();
		}
		else{
			while(ops.size() && mp[ops.top()]>=mp[i]){
				res.pb(c2str(ops.top()));
				ops.pop();
			}
			ops.push(i);
		}
	}
	while(ops.size()) res.pb(c2str(ops.top())), ops.pop();
	return res;
}

int to_int(string s){
	int res=0;
	for(auto i: s) res=res*10+i-'0';
	return res;
}

int getV(int a, int b, string op){
	if(op=="+") return a+b;
	if(op=="-") return a-b;
	if(op=="*") return a*b;
	if(op=="/") return a/b;
	if(op=="^"){
		int res=1;
		for(; b; b>>=1, a*=a) if(b&1) res=res*a;
		return res;
	}
}

int cal(vector<string> s){
	stack<int> stk;
	for(auto i: s){
		if(!mp.count(i[0])) stk.push(to_int(i));
		else{
			int a=stk.top(); stk.pop();
			int b=stk.top(); stk.pop();
			stk.push(getV(b, a, i));
		}
	}
	return stk.top();
}

signed main(){
	mp['(']=0;
	mp['+']=mp['-']=1;
	mp['*']=mp['/']=2;
	mp['^']=3;

	string str; cin>>str;
	string s;
	rep(i,0,str.size()-1){
		if(i && str[i]=='-' && !isdigit(str[i-1]) || !i && str[i]=='-'){
			if(i && str[i-1]==')') s+="+(0-1)*";
			else s+="(0-1)*";
		}
		else s+=str[i];
	}
	
	int cntL=0, cntR=0;
	for(auto i: s){
		if(i=='(') cntL++;
		else if(i==')' && cntL) cntL--;
		else if(i==')' && !cntL) cntR++;
	}
	while(cntL--) s+=')';
	auto tmp=s;
	s="";
	while(cntR--) s+='(';
	s+=tmp; 
	
	cout<<cal(get(s))<<endl;
	
	return 0;
}

【模拟 + 栈】AcWing 151. 表达式计算4

分析

实现

推荐阅读