即建立一个运算符栈,一个数栈,先处理掉所有的负号(优先级最高),特判括号。
当且仅当栈顶运算符优先级低于新运算符时,新运算符进栈。
注意我这里有错误,为了方便将乘方与负号优先级设为相等,毕竟两道题不一样233.
talk is cheap, show me the code=v=
#include<iostream>
#include<cstdio>
#include<stack>
#include<cmath>
#include<cctype>
using namespace std;
stack<int> num;
stack<char> ope;
string s;
int len, flag, innum;
int priority(char c)
{
if(c=='$' || c=='^') return 3;
if(c=='*' || c=='/') return 2;
if(c=='+' || c=='-') return 1;
else return 0;
}
bool isope(char c) //judge the argue
{
switch(c)
{
case '+':case '-':case '*':case '/': return 1;
default: return 0;
}
}
int pre_the_expression() //preperation expression
{
cin>>s;
len=s.length()-1; //the last question you should change the length
int pos=-1;
while((pos=s.find('-', pos+1))!=string::npos)
if(priority(s[pos-1]) || s[pos-1]=='(' || pos==0) s[pos]='$';
for(int i=1; i<len; i++)
if(isope(s[i]) && isope(s[i+1])) return 1;
return 0;
}
void pop_num()
{
char c=ope.top(); ope.pop();
int n1=num.top(); num.pop();
if(c=='$') num.push(n1*-1); //single ope
else
{
int n2=num.top(); num.pop();
switch(c)
{
case '+': num.push(n2+n1); break;
case '-': num.push(n2-n1); break;
case '*': num.push(n2*n1); break;
case '/': num.push(n2/n1); break;
case '^': num.push(pow(n2, n1)); break;
}
}
}
int main()
{
//freopen("in.txt", "r", stdin);
if(pre_the_expression()) //too many opes
{
printf("NO");
return 0;
}
for(int i=0; i<len; i++) //work
{
if(isdigit(s[i])) //digit
{
innum=s[i]-'0';
while(isdigit(s[i+1]))
{
i++;
innum=innum*10+s[i]-'0';
}
num.push(innum);
continue;
}
else if(s[i]=='(') ope.push('(');
else if(s[i]==')') //()
{
while(ope.top()!='(' && !ope.empty())
pop_num(); //wrong ()
if(ope.empty()) {flag=1;break;}
else ope.pop();
}
else //the opes
{
while(!ope.empty() && priority(s[i])<=priority(ope.top()))
pop_num();
ope.push(s[i]);
}
}
while(!ope.empty()) pop_num();
if(flag) printf("NO");
else printf("%d", num.top());
return 0;
}