20求条
查看原帖
20求条
1433656
I_do_Cpp楼主2025/6/22 14:11
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool isNumber(string s)//判断是否是数字
{
	return (s!="+" && s!="-"&&s!="*"&&s!="/"&&s!="("&&s!=")");
}
ll evaluatePostfix(vector<string> token)//后缀表达式的计算
{
	stack<ll> st;
	for(string s:token)
	{
		if(s.empty())continue;
		if(s=="+" or s=="-" or s=="*" or s=="/" or s=="^")
		{
			ll num2=st.top();
			st.pop();
			ll num1=st.top();
			st.pop();
			if(s=="+")
			{
				st.push(num1+num2);
			}
			else if(s=="-")
			{
				st.push(num1-num2);
			}
			else if(s=="*")
			{
				st.push(num1*num2);
			}
			else if(s=="/")
			{
				st.push(num1/num2);
			}
			else if(s=="^")
			{
				ll ans=1;
				for(ll i=1;i<=num2;i++)
				{
					ans*=num1;
				}
				st.push(ans);
			}
		}
		else
		{
			st.push(stoll(s));
		}
	}
	return st.top();
}
ll preceduce(string opr)//判断优先级
{
	if(opr=="+"||opr=="-")return 1;
	else if(opr=="*"||opr=="/")return 2;
	else if(opr=="^")return 3;
	else return 0;
}
vector<string> infixToPostfix(vector<string> token)//把中缀表达式转成后缀表达式
{
	stack<string> st;
	vector<string> postfix;
	for(int i=0;i<token.size();i++)
	{
		string s=token[i];
		if(s.empty()) continue; 
		if(isNumber(s)) 
		{
		    postfix.push_back(s);
		}
		else if(s=="(")
		{
			st.push(s);
		}
		else if(s==")")
		{
			while( st.empty()==false&&st.top()!="(")
			{
				postfix.push_back(st.top());
				st.pop();
			}
			
			if(!st.empty())st.pop();
		}
		else
		{
			while(st.empty()==false&&preceduce(st.top())>=preceduce(s))
			{
				postfix.push_back(st.top());
				st.pop();
			}
			st.push(s);
		}
	}
	while(st.empty()==false)
	{
		postfix.push_back(st.top());
		st.pop();
	}
	return postfix;
}
int main()
{
	vector<string> infix;
	string s;
	getline(cin,s);
	string word="";
	ll c1=0,c2=0;
	for(ll i=0;i<s.size();i++)
	{
		string c="";
		c+=s[i];
		if(c=="+"||c=="-"||c=="*"||c=="/"||c=="^"||c==")")
		{
			if(c==")")c2++;
			if((c=="-" or c=="+")&&(word==""||word=="-"||word=="+"))
			{
				if(infix.size()==0)
				{
					if(word=="")word+=c;
					else if(word==c)word="";
					else word="-";
					continue;
				}
				string last=infix[infix.size()-1];
				if((last!=")")&&(!isNumber(last)))
				{
					if(word=="")word+=c;
					else if((word=="+"&&c=="-")||(word=="-"||c=="+"))word="-";
					else word="";
					continue;
				}
			}
			infix.push_back(word);
			infix.push_back(c);
			word="";
		}
		else if(c=="(")c1++;
		else
		{
			word+=c;
		}
	}
	if(word!="")
	{
		infix.push_back(word);
	}
	if(c1-c2>0)
	{
		for(int i=0;i<c1-c2;i++)
		{
			infix.push_back(")");
		}
	}
	else
	{
		for(int i=0;i<c2-c1;i++)
		{
			infix.insert(infix.begin(),"(");
		}
	}
	vector<string> ans=infixToPostfix(infix);
	//for(string k:ans)cout<<k<<" ";
	
	cout<<evaluatePostfix(ans)<<endl;
	return 0;
}
2025/6/22 14:11
加载中...