一本通3.1栈蓝色线：2020.3.8
1331：特简单，方法都给了，直接上代码
#include <bits/stdc++.h>
using namespace std;
stack<long long> ss;
char ch;
long long t;
int main()
{
cin>>ch;
while(ch!='@')
{
if(ch>='0'&&ch<='9')
{
t=t*10+ch-48;
}
else if(ch==' ')
{
ss.push(t);
t=0;
}
else
{
long long x=ss.top();
ss.pop();
long long y=ss.top();
ss.pop();
switch(ch)
{
case '+':
ss.push(x+y);
break;
case '-':
ss.push(y-x);
break;
case '*':
ss.push(x*y);
break;
case '/':
ss.push(y/x);
break;
}
}
scanf("%c",&ch);
}
cout<<ss.top()<<endl;
return 0;
}
提醒一下：注意longlong，小心栽坑。
1356：稍微有点难度，我花了1小时，注意乘方：
3^1*2=6,3^(1*2)=9
还有优先级的使用
代码：
#include <bits/stdc++.h>
using namespace std;
char s[100050];
stack<char> s1;
stack<long long> s2;
long long t=0;
bool flag;
void go()
{
int x=s2.top();
s2.pop();
int y=s2.top();
s2.pop();
switch(s1.top())
{
case '+':
s2.push(x+y);
break;
case '-':
s2.push(y-x);
break;
case '*':
s2.push(x*y);
break;
case '/':
s2.push(y/x);
break;
case '^':
s2.push(pow(y,x));
break;
}
s1.pop();
}
bool ca(int k)
{
if(s1.empty()) return 0;
if(s1.top()=='^') return 1;
if((s[k]=='+'||s[k]=='-')&&s1.top()!='(') return 1;
if((s[k]=='*'||s[k]=='/')&&(s1.top()=='*'||s1.top()=='/')) return 1;
return 0;
}
int main()
{
cin>>s;
s[strlen(s)]='w';
for(int i=0; i<strlen(s); i++)
{
if(s[i]>='0'&&s[i]<='9')
{
t=t*10+s[i]-48;
flag=1;
}
else
{
if(flag)
{
s2.push(t);
t=0;
flag=0;
}
if(s[i]=='(') s1.push(s[i]);
if(s[i]==')')
{
while(s1.top()!='(')
go();
s1.pop();
}
if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='^')
{
while(ca(i)) go();
s1.push(s[i]);
}
if(s[i]=='w')
{
while(!s1.empty())go();
}
}
}
cout<<s2.top()<<endl;
return 0;
}
最后是1358：类似1356，稍微改动
#include <bits/stdc++.h>
using namespace std;
char s[100050];
stack<char> s1;
stack<long long> s2;
long long t=0;
bool flag,ff;
void go()
{
int x=s2.top();
s2.pop();
int y=s2.top();
s2.pop();
switch(s1.top())
{
case '+':
s2.push(x+y);
break;
case '-':
s2.push(y-x);
break;
case '*':
s2.push(x*y);
break;
case '/':
s2.push(y/x);
break;
case '^':
s2.push(pow(y,x));
break;
}
s1.pop();
}
bool judge()
{
int tot=0,i=0;
while(i<strlen(s)-1)
{
if(s[i]=='(') tot++;
if(s[i]==')')
{
if(tot==0) return 1;
tot--;
}
if(s[i]=='+'||s[i]=='*'||s[i]=='/'||s[i]=='^'||s[i]==')')
if(s[i-1]=='+'||s[i-1]=='*'||s[i-1]=='/'||s[i-1]=='^'||s[i-1]=='('||s[i]=='-')
return true;
i++;
}
if(tot==0) return 0;
return 1;
}
bool ca(int k)
{
if(s1.empty()) return 0;
if(s1.top()=='^') return 1;
if((s[k]=='+'||s[k]=='-')&&s1.top()!='(') return 1;
if((s[k]=='*'||s[k]=='/')&&(s1.top()=='*'||s1.top()=='/')) return 1;
return 0;
}
int main()
{
cin>>s;
if(judge())
{
cout<<"NO"<<endl;
return 0;
}
if(s[strlen(s)-1]!='@') s[strlen(s)]='@';
for(int i=0; i<=strlen(s); i++)
{
if(s[i]>='0'&&s[i]<='9')
{
t=t*10+s[i]-48;
flag=1;
if(i!=0&&s[i-1]=='-')
if(i==1||s[i-2]=='+'||s[i-2]=='-'||s[i-2]=='*'||s[i-2]=='/'||s[i-2]=='^'||s[i-2]=='(')
ff=true;
}
else
{
if(flag)
{
if(ff) t=-t;
s2.push(t);
t=0;
flag=0;
ff=0;
}
if(s[i]=='(') s1.push(s[i]);
if(s[i]==')')
{
while(s1.top()!='(')
go();
s1.pop();
}
if(s[i]=='+'||(s[i]=='-'&&(s[i-1]!='+'&&s[i-1]!='-'&&s[i-1]!='*'&&s[i-1]!='/'&&s[i-1]!='^'
&&s[i-1]!='('&&i!=0))||s[i]=='*'||s[i]=='/'||s[i]=='^')
{
while(ca(i)) go();
s1.push(s[i]);
}
if(s[i]=='@')
while(!s1.empty()) go();
}
}
cout<<s2.top()<<endl;
return 0;
}
提示：注意这个‘-’号带来的影响：一定要考虑周全，不然易失分。这里有点错位，在倒数第8、9行，抄代码时注意【呵呵一笑】。
总结：这三题，以后缀表达式为最简单，中缀表达式相对较难，但是只要熟练地运用栈，也可以避免出现问题。更要注意“坑”。
