单调栈（洛谷P5788）
题目大意
与栈中的向右看齐相同
题解
未知的代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5;
int a[N],ans[N],n;
stack<int>s;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n;i>=1;i--){
while(!s.empty()&&a[s.top()]<=a[i])s.pop();
if(s.empty())ans[i]=0;
else ans[i]=s.top();
s.push(i);
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
return 0;
}
后缀表达式（洛谷P1449）
题目大意
计算后缀表达式的值
解题思路
利用栈计算后缀表达式
未知的代码
#include<bits/stdc++.h>
using namespace std;
string s;
stack<string>st;
int main(){
getline(cin,s);
int p=0;
while(s[p]!='@'){
string tmp;
while(s[p]!='.'&&isdigit(s[p]))tmp+=s[p++];
if(s[p]!='.'){
int a=stoi(st.top());st.pop();
int b=stoi(st.top());st.pop();
switch(s[p]){
case '+':st.push(to_string(b+a));break;
case '-':st.push(to_string(b-a));break;
case '*':st.push(to_string(b*a));break;
case '/':st.push(to_string(b/a));break;
}
}
else st.push(tmp);
p++;
}
cout<<st.top();
return 0;
}
表达式括号匹配（洛谷P1739）
题目大意
判断表达式括号是否匹配。
解题思路
利用栈存入括号，当遇到右括号时出栈匹配是否为左括号。
未知的代码
#include<bits/stdc++.h>
using namespace std;
string s;
stack<char>st;
int main(){
getline(cin,s);
for(auto&ch:s){
if(ch=='(')st.push(ch);
else if(ch==')'){
if(!st.empty()&&st.top()=='(')st.pop();
else{
puts("NO");
return 0;
}
}
}
if(st.empty())puts("YES");
else puts("NO");
return 0;
}
表达式求值（P1981）
题目大意
对一个字符串算数表达式计算求值。表达式只有加法和乘法，不含括号。
解题思路
先将所有乘法计算出来，转化为只有加法，最后相加求解。
未知的代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e4;
stack<int>s;
int main(){
int a,b;
char op;
cin>>a;
s.push(a%mod);
while(cin>>op>>b){
if(op=='+')s.push(b);
else{
a=s.top();
s.pop();
s.push(a*b%mod);
}
}
a=0;
while(!s.empty()){
a+=s.top();
s.pop();
}
cout<<a%mod<<endl;
return 0;
}
表达式的转换（P1175）
题目大意
给定中缀表达式，输出转化后缀表达式后的每一次运算操作后的后缀表达式。
解题思路
先将中缀表达式转为后缀表达式，需要考虑运算符优先级，然后按优先级顺序和先后顺序依次计算并输出。对于给定的中缀表达式字符串s，遍历每个字符，根据字符的类型进行相应的操作：如果是数字，则直接添加到结果字符串；如果是'('，则将其压入栈中；如果是')'，则将栈顶元素弹出并添加到结果字符串，直到遇到'('，然后将'('从栈中弹出；如果是运算符，则比较其与栈顶运算符的优先级，如果栈顶运算符优先级高于等于当前运算符，则将栈顶元素弹出并添加到结果字符串，直到栈为空或栈顶运算符优先级低于当前运算符，然后将当前运算符压入栈中。最后，将栈中剩余的运算符依次弹出并添加到结果字符串。
未知的代码
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
auto priority=[&](char c){
switch(c){
case '+':
case '-':return 1;
case '*':
case '/':return 2;
case '^':return 3;
case '(':
case ')':return 0;
default:return -1;
}
};
auto to_suffix=[&](string&s){
string ans;
stack<char>st;
for(auto&it:s){
if(isdigit(it))ans+=it;
else if(it=='(')st.push(it);
else if(it==')'){
while(!st.empty()&&st.top()!='('){
ans+=st.top();
st.pop();
}
if(!st.empty())st.pop();
}else{
while(!st.empty()&&priority(st.top())>=priority(it)){
if(priority(st.top())==priority(it)&&it=='^')break;
ans+=st.top();
st.pop();
}
st.push(it);
}
}
while(!st.empty()){
ans+=st.top();
st.pop();
}
return ans;
};
auto calc_part=[&](int a,int b,char op){
switch(op){
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
case '/': return a/b;
case '^': return (int)pow(a,b);
default: return -1;
}
};
auto calc=[&](string s){
vector<int>l;
for(auto&it:s)cout<<it<<' ';
cout<<endl;
for(auto it=s.begin();it!=s.end();it++){
if(isdigit(*it))l.push_back(*it-'0');
else{
int a=l.back();
l.pop_back();
int b=l.back();
l.pop_back();
l.push_back(calc_part(b,a,*it));
for(auto&v:l)cout<<v<<' ';
for(auto jt=it+1;jt!=s.end();jt++)cout<<*jt<<" ";
cout<<endl;
}
}
};
calc(to_suffix(s));
return 0;
}