数据结构-栈的应用（括号匹配，表达式求值（中缀转后缀、中缀表达式））
中缀表达式求值模板
/*
中缀表达式求值 模板
如何判断某棵子树被遍历完
往上走意味被遍历完，往下走意味着未遍历完
当前运算符的优先级只要<=上一个运算符的优先级，操作一下
考虑右括号 ，括号内的优先级是往下走的，所以括号内运算符优先级是递增的，从右往左算，
*/
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
int n,m;
stack<int>num;
stack<char>op;
void eval()//操作最后一个运算符
{
int a=num.top();num.pop();
int b=num.top();num.pop();
char c=op.top();op.pop();
int x=0;
if(c=='+') x=b+a;
else if(c=='-') x=b-a;
else if(c=='*') x=b*a;
else if(c=='/') x=b/a;
num.push(x);
}
void solve()
{
//利用哈希表定义优先级
unordered_map<char,int>pr{{'+',1},{'-',1},{'*',2},{'/',2}};
string s;
cin>>s;
int i,j;
for(i=0;i<s.size();i++)
{
auto c=s[i];
if(isdigit(c))
{
int tol=0;
j=i;//j从i开始走
while(j<s.size()&&isdigit(s[j]))//并且j一边走，s[j]是数字的话
{
tol=tol*10+s[j++]-'0';
}
i=j-1;
num.push(tol);
}
else if(s[i]=='(')//如果当前字符是左括号的话
{
op.push(s[i]);
}
else if(s[i]==')')//就应该把栈里的所有运算符从右向左操作一遍，直到遇到左括号为止
{
while(op.top()!='(') eval();//用末尾的运算符去操作末尾的两个数
op.pop();//将左括号弹出
}
else//再比如是一般的运算符
{
while(op.size()&&pr[op.top()]>=pr[c])//栈不为空，并且栈顶的运算符的优先级大于当前运算符的优先级
eval();
op.push(c);//否则就将当前的运算符插入栈中
}
}
while(op.size()) eval() ;//最后再将没有操作完的运算符从右往左操作一遍
cout<<num.top()<<endl;
}
signed main()
{
int t=1;
while(t--)
{
solve();
}
return 0;
}
中缀表达式求值模板以及判断该表达式是否合法
/*
中缀表达式求值 模板
如何判断某棵子树被遍历完
往上走意味被遍历完，往下走意味着未遍历完
当前运算符的优先级只要<=上一个运算符的优先级，操作一下
考虑右括号 ，括号内的优先级是往下走的，所以括号内运算符优先级是递增的，从右往左算，
判断表达式是否合法
*/
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
int n,m;
stack<int>num;
stack<char>op;
//利用哈希表定义优先级
unordered_map<char,int>pr {{'+',1},{'-',1},{'*',2},{'/',2}};
string s;
//priority_queue<int,vector<int>,greater<int>>q;
bool check(char c)
{
if(c=='+'||c=='-'||c=='*'||c=='/')
return true;
else
return false;
}
bool judge()
{
stack<char>stk;
int i,j;
for(int i=0;i<s.size();i++)
{
if(s[i]=='@')
break;
if(s[i]=='(')
stk.push(s[i]);
else if(s[i]==')')
{
if(stk.empty())
return false;
stk.pop();
}
}
if(!stk.empty()) return false;
//如果右两个连续的运算符是不合法的
for(i=0;i<s.size()-1;i++)//除去@遍历整个s
{
if(check(s[i])&&check(s[i+1]))
return false;
}
return true;
}
void eval()//操作最后一个运算符
{
int a=num.top();
num.pop();
int b=num.top();
num.pop();
char c=op.top();
op.pop();
int x=0;
if(c=='+') x=b+a;
else if(c=='-') x=b-a;
else if(c=='*') x=b*a;
else if(c=='/') x=b/a;
num.push(x);
}
void solve()
{
cin>>s;
if(!judge())
{
cout<<"NO"<<endl;
return;
}
int i,j;
for(i=0; i<s.size(); i++)
{
auto c=s[i];
if(s[i]=='@')
break;
if(isdigit(c))
{
int tol=0;
j=i;//j从i开始走
while(j<s.size()&&isdigit(s[j]))//并且j一边走，s[j]是数字的话
{
tol=tol*10+s[j++]-'0';
}
i=j-1;
num.push(tol);
}
else if(s[i]=='(')//如果当前字符是左括号的话
{
op.push(s[i]);
}
else if(s[i]==')')//就应该把栈里的所有运算符从右向左操作一遍，直到遇到左括号为止
{
while(op.top()!='(') eval();//用末尾的运算符去操作末尾的两个数
op.pop();//将左括号弹出
}
else//再比如是一般的运算符
{
while(op.size()&&pr[op.top()]>=pr[c])//栈不为空，并且栈顶的运算符的优先级大于当前运算符的优先级
eval();
op.push(c);//否则就将当前的运算符插入栈中
}
}
while(op.size()) eval() ;//最后再将没有操作完的运算符从右往左操作一遍
cout<<num.top()<<endl;
}
signed main()
{
int t=1;
while(t--)
{
solve();
}
return 0;
}后缀表达式求值
/*
后缀表达式求值
*/
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
int n,m;
void solve()
{
string ss;
getline(cin,ss);
stack<int>s;
int i,j;
for(i=0;i<ss.size();i++)
{
auto c=ss[i];
if(c=='@')//以@结尾 结束
break;
else if(isdigit(c))
{
int num=0;
j=i;
while(j<ss.size()&&isdigit(ss[j]))
{
num=num*10+ss[j++]-'0';
}
s.push(num);
i=j-1;
}
else if(c==' ')
{
continue;
}
else
{
int a=s.top();//ps先弹出的是右操作数
s.pop();
int b=s.top();//ps后弹出的是左操作数
s.pop();
if(ss[i]=='*') s.push(b*a);
if(ss[i]=='/') s.push(b/a);
if(ss[i]=='+') s.push(b+a);
if(ss[i]=='-') s.push(b-a);
}
}
cout<<s.top()<<endl;
}
signed main()
{
int t=1;
while(t--)
{
solve();
}
return 0;
}
括号匹配
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
int n,m;
//priority_queue<int,vector<int>,greater<int>>q;
void solve()
{
string s;
cin>>s;
int i,j;
stack<char>stk;
int f=0;
for(i=0;i<s.size();i++)
{
if(s[i]=='('||s[i]=='[')
{
stk.push(s[i]);
}
else
{
if(stk.size())
{
if(s[i]==')'&&stk.top()=='(')
{
stk.pop();
}
else if(s[i]==']'&&stk.top()=='[')
{
stk.pop();
}
else
{
f=1;
}
}
else
f=1;
}
}
// cout<<f<<endl;
// cout<<stk.size()<<endl;
if(f==0&&stk.size()==0)
cout<<"OK"<<endl;
else
cout<<"WRONG"<<endl;
}
signed main()
{
int t=1;
while(t--)
{
solve();
}
return 0;
}