#include<bits/stdc++.h>

using namespace std;

bool isBracketValid(char s[])

{

stack<char> stk; 
for(int i = 0; i < strlen(s); ++i)
{
	if(s[i] == '(')
		stk.push(s[i]);
	else if(s[i] == ')')
	{
		if(stk.empty() == false)
			stk.pop();
		else
			return false; 
	}
}
if(stk.empty() == false)
	return false;
else
	return true;

} void strInsert(char s[], int x, char c) { for(int i = strlen(s); i >=x; --i) { s[i+1] = s[i]; } s[x] = c; } void addZero(char s[]) { if(s[0] == '-') strInsert(s, 0, '0'); for(int i = strlen(s)-1; i >= 1; --i) { if(s[i] == '-' && s[i-1] == '(') strInsert(s, i, '0'); } } bool isCal(char c) { if(c == '+' || c == '-' || c == '*' ||c == '/' || c == '(' || c == ')') return true; else return false; }

bool isCalValid(char s[]) { int len = strlen(s); if(isCal(s[0]) && s[0]!='(') return false; if(isCal(s[len-1]) && s[len-1]!=')') return false; for(int i = 1; i < strlen(s); ++i) { if(isCal(s[i]) && isCal(s[i-1])) { if(s[i-1] == ')' && s[i] == '(') return false; else if(s[i-1] == ')' || s[i] == '(') ; else return false; } } return true; } bool isValid(char s[]) { if(isBracketValid(s) == false) return false; addZero(s); if(isCalValid(s)) return true; else return false; } int getCalNum(char c) { switch(c) { case ')': return 1; case '+': case '-': return 2; case '': case '/': return 3; case '^': return 4; case '(': return 5; } } bool isSuperior(char c1, char c2) { return getCalNum(c1) > getCalNum(c2); } int calc(int a, int b, char c) { switch(c) { case '+': return a+b; case '-': return a-b; case '': return a*b; case '/': return a/b; } } int calToInt(char c) { return -(int)c; } char intToCal(int a) { return char(-a); } void printPstExp(vector s) { for(int i = 0; i < s.size(); ++i) { if(s[i] < 0) cout<<intToCal(s[i])<<' '; else cout<<s[i]<<' '; } cout<<endl; } //计 int calcPstExp(vector s) { stack stk; for(int i = 0; i < s.size(); ++i) { if(s[i] >= 0) stk.push(s[i]); else { int b = stk.top(); stk.pop(); int a = stk.top(); stk.pop(); char c = intToCal(s[i]); stk.push(calc(a, b, c)); } } return stk.top(); }

int main() { int n, num = 0; char s[1000]; bool isForming = false; vector pstExp; cin>>s; s[strlen(s)-1] = '\0'; if(isValid(s) == false) { cout<<"NO"; return 0; }

s[strlen(s)+1] = '\0';
s[strlen(s)] = ')';	

stack<char> stk_cal;
for(int i = 0; i < strlen(s); ++i)
{
	if(s[i] >= '0' && s[i] <= '9')
	{
		isForming = true;
		num = num * 10 + s[i] - '0';
	}
	else
	{
		if(isForming)
		{
			pstExp.push_back(num);
			num = 0;
			isForming = false;
		}
		do
		{  
			if(stk_cal.empty() || isSuperior(s[i], stk_cal.top()))
			{
				stk_cal.push(s[i]);
				break;
			}
			else if(stk_cal.top() == '(')
			{
				if(s[i] == ')')
					stk_cal.pop();
				else
					stk_cal.push(s[i]);
				break;
			}
			else 
			{
				pstExp.push_back(calToInt(stk_cal.top()));
				stk_cal.pop();
			}
		}while(true);
	}
}
cout<<calcPstExp(pstExp); 
return 0;

}

1 条评论

  • @ 2025-3-14 15:52:46

    你写了些啥???????????????????????????????????????????????????????????????????????????????????????????

    • 1

    信息

    ID
    361
    时间
    ms
    内存
    MiB
    难度
    10
    标签
    递交数
    8
    已通过
    1
    上传者