表达式类型问题
P1981 [NOIP2013 普及组] 表达式求值
思路
本题题目中保证了，不会出现括号，那么就很好解决了。但是输入用字符串不太好处理，所以，我们采用另一种输入方法：while(cin)。
观察题目中的输入，我们发现可以这样拆分：
先读入一个数字，压入栈中，再读入一个字符和一个数字，将数字压入栈中，然后对栈顶的两个元素进行输入的字符的操作，最后将栈内所有元素相加，输出这个和就行了。
因为要保留后
Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
char c;
int sum;
stack<int> st;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>sum;
st.push(sum);
while(cin>>c>>sum)
{
if(c=='+') st.push(sum%10000);
else if(c=='*')
{
st.top()*=sum;
st.top()%=10000;
}
}
int ans=0;
while(!st.empty())
{
ans+=st.top();
ans%=10000;
st.pop();
}
cout<<ans;
return 0;
}P1449 后缀表达式
思路
题目中给出了后缀表达式的定义以及运算过程，所以，我们可以直接进行模拟。计算器也是用的后缀表达式。
直接将数字全部压入栈中，遇到运算符就对栈顶的两个元素进行运算。
后缀表达式：运算简单，运算符和数字个数位置不固定。
Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum;
string s;
stack<int> stk;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>s;
for(int i=0;i<s.size();++i)
{
if(s[i]>='0'&&s[i]<='9') sum=sum*10+s[i]-'0';
else if(s[i]=='.') stk.push(sum),sum=0;
else if(s[i]!='@')
{
int y=stk.top();
stk.pop();
int x=stk.top();
stk.pop();
if(s[i]=='+') stk.push(x+y);
else if(s[i]=='-') stk.push(x-y);
else if(s[i]=='*') stk.push(x*y);
else if(s[i]=='/') stk.push(x/y);
}
}
cout<<stk.top();
return 0;
}D1352 中缀表达式值(expr)
思路
这题有括号了，难度直接飙升。
我们先来看不合法的情况：
-
括号不匹配。
-
出现了
++等不合法的运算符。
本题中只需要考虑这两种情况，所以，我们直接把括号匹配的代码搬过来，然后再判断是不是连续两个字符都是运算符就行了。
接下来就要给运算符赋值优先级：
注意，左括号一定是
接下来就到了最麻烦的中缀表达式转后缀表达式了。
转换规则
下列的输出表示得到当前位的后缀表达式字符或数字。
-
如果是数字，直接输出。
-
如果是左括号，压入栈中然后什么都不做。
-
如果当前位是运算符，将栈顶优先级大于等于当前运算符的全部弹出然后输出，将当前符号压入栈中。
-
如果是右括号，一直输出，弹出直到遇到第一个左括号，将两个括号抵消。
-
如果还有剩余的，全部输出。
然后，我们在主函数中循环每一位，如果是数字，输出，否则 check 当前字符，就是按照规则进行。
对于输出的结果，我们用一个结构体储存，其变量分别是如下作用：
| 用于储存是不是数字， |
|
|---|---|
| 储存字符 | |
| 储存数字 |
然后按照后缀表达式进行计算即可。
我的函数名一点都不奇怪。
Code:
#include<bits/stdc++.h>
using namespace std;
int cnt;
string s;
map<char,int> mp;
stack<char> f;
struct no{
bool f;
char c;
int num;
}a[1005];
bool BUMIE_sieve(char c);
bool check_is_bumie();
void init();
void add(int x,char c,bool f);
void check(char c);
void compute();
int BUMIE(int x,int y,char op);
int main()
{
init();
cin>>s;
if(!check_is_bumie())
{
cout<<"NO";
return 0;
}
int len=s.size();
for(int i=0;i<len;++i)
{
if(s[i]>='0'&&s[i]<='9') add(s[i]-'0',' ',true);
else check(s[i]);
}
while(!f.empty())
{
char ch=f.top();
f.pop();
add(0,ch,0);
}
compute();
return 0;
}
bool BUMIE_sieve(char c){return c=='+'||c=='-'||c=='/'||c=='*';}
bool check_is_bumie()
{
stack<char> stk;
int len=s.size();
for(int i=0;i<len;++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(int i=0;i<len-1;++i)
{
if(BUMIE_sieve(s[i])&&BUMIE_sieve(s[i+1]))
{
return false;
}
}
return true;
}
void init()
{
mp['+']=1;
mp['-']=1;
mp['*']=2;
mp['/']=2;
mp['(']=0;
return;
}
void add(int x,char c,bool f)
{
a[++cnt]={f,c,x};
return;
}
void check(char c)
{
if(c=='@') return;
if(c=='(') f.push(c);
else if(c==')')
{
while(f.top()!='(')
{
add(0,f.top(),0);
f.pop();
}
f.pop();
}
else
{
if(f.empty()) f.push(c);
else
{
while(!f.empty())
{
char ch=f.top();
if(mp[ch]>=mp[c])
{
add(0,ch,0);
f.pop();
}
else break;
}
f.push(c);
}
}
return;
}
void compute()
{
stack<int> stk;
for(int i=1;i<=cnt;++i)
{
if(a[i].f)
{
stk.push(a[i].num);
}
else
{
int y=stk.top();
stk.pop();
int x=stk.top();
stk.pop();
stk.push(BUMIE(x,y,a[i].c));
}
}
cout<<stk.top();
return;
}
int BUMIE(int x,int y,char op)
{
int ans=0;
if(op=='+') ans=x+y;
if(op=='-') ans=x-y;
if(op=='*') ans=x*y;
if(op=='/') ans=x/y;
return ans;
}P1175 表达式的转换
思路
如果上一题掌握了，这题基本思路就有了。
我们写一个 print 函数，用于输出当前的结果。
我们在每一次运算的时候，将结果输出一次，但是用数组的下标不好控制，于是，我们就想到了
我们每次将参与运算的
但是，这题里还有一个「乘方」操作，「乘方」操作的优先级要大于乘除，所以，它的优先级是
注意，
Code:
#include<bits/stdc++.h>
using namespace std;
int cnt;
string s;
map<char,int> mp;
stack<char> f;
struct no{
bool f;
char c;
int num;
};
vector<no> vec;
bool BUMIE_sieve(char c);
bool check_is_bumie();
void init();
void add(int x,char c,bool f);
void check(char c);
void compute();
int BUMIE(int x,int y,char op);
void print();
int main()
{
init();
cin>>s;
// if(!check_is_bumie())
// {
// cout<<"NO";
// return 0;
// }
int len=s.size();
for(int i=0;i<len;++i)
{
if(s[i]>='0'&&s[i]<='9') add(s[i]-'0',' ',true);
else check(s[i]);
}
while(!f.empty())
{
char ch=f.top();
f.pop();
add(0,ch,0);
}
print();
compute();
return 0;
}
bool BUMIE_sieve(char c){return c=='+'||c=='-'||c=='/'||c=='*'||c=='^';}
bool check_is_bumie()
{
stack<char> stk;
int len=s.size();
for(int i=0;i<len;++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(int i=0;i<len-1;++i)
{
if(BUMIE_sieve(s[i])&&BUMIE_sieve(s[i+1]))
{
return false;
}
}
return true;
}
void init()
{
mp['+']=1;
mp['-']=1;
mp['*']=2;
mp['/']=2;
mp['^']=3;
mp['(']=0;
return;
}
void add(int x,char c,bool f)
{
cnt++;
vec.push_back({f,c,x});
return;
}
void check(char c)
{
if(c=='@') return;
if(c=='(') f.push(c);
else if(c==')')
{
while(!f.empty()&&f.top()!='(')
{
add(0,f.top(),0);
f.pop();
}
f.pop();
}
else if(c=='^')
{
while(!f.empty()&&mp[f.top()]>mp[c])
{
add(0,f.top(),0);
f.pop();
}
f.push(c);
}
else
{
if(f.empty()) f.push(c);
else
{
while(!f.empty())
{
char ch=f.top();
if(mp[ch]>=mp[c])
{
add(0,ch,0);
f.pop();
}
else break;
}
f.push(c);
}
}
return;
}
int BUMIE(int x,int y,char op)
{
int ans=0;
if(op=='+') ans=x+y;
if(op=='-') ans=x-y;
if(op=='*') ans=x*y;
if(op=='/') ans=x/y;
if(op=='^')
{
ans=1;
while(y--) ans*=x;
}
return ans;
}
void compute()
{
for(int i=0;i<cnt;++i)
{
if(!vec[i].f)
{
int y=vec[i-1].num;
int x=vec[i-2].num;
char op=vec[i].c;
vec.erase(vec.begin()+i-2);
vec.erase(vec.begin()+i-2);
vec.erase(vec.begin()+i-2);
int tmp=BUMIE(x,y,op);
i-=2;
vec.insert(vec.begin()+i,{true,' ',tmp});
cnt-=2;
print();
}
}
return;
}
void print()
{
for(int i=0;i<cnt;++i)
{
if(vec[i].f) cout<<vec[i].num<<' ';
else cout<<vec[i].c<<' ';
}
cout<<'\n';
return;
}