算法总结—表达式

LRRabcd · 2024-10-18 21:53:02 · 算法·理论

表达式求值

我们可以先处理乘法在处理加法：

• 如果当前的运算符 c_i 为乘号，将 a_i 乘上 a_{i+1} ，并把 a_{i+1} 归零。

• 最后把所有 a_i 的值加起来。

由于是 a_i\times a_{i+1} 所以数字要从后往前枚举。

记得取模 10000。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[50005];
char c[50005];
signed main(){
    int cnt=1;
    cin>>a[cnt];
    a[1]%=10000;
    while(cin>>c[cnt]>>a[cnt+1]){
        cnt++;
        a[cnt]%=10000;
    } 
    for(int i=cnt;i>=1;i--){
        if(c[i]=='*'){
            a[i]*=a[i+1];
            a[i]%=10000;
            a[i+1]=0;
        }
    }
    int ans=0;
    for(int i=1;i<=cnt;i++){
        ans+=a[i];
        ans%=10000;
    }
    cout<<ans; 
    return 0;
}

后缀表达式

直接用栈处理即可：

• 若 s_i 为数字，用一个变量白塔加起来。

• 若 s_i 为字符 .，将上一个数字压入栈中，并将储存数字的变量清零。

• 若 s_i 为 +,-,*,/，取出栈顶的量个运算符，把它们运算好后重新压入栈中，如果是减法或除法就是将栈顶第二个元素去减或除栈顶第一个元素。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
stack<int>st;
signed main(){
    string s;
    cin>>s;
    while(s.back()=='@'){
        s.pop_back();
    }
    int len=s.size();
    int num=0;
    for(int i=0;i<len;i++){
        if(s[i]>='0'&&s[i]<='9'){
            num*=10;
            num+=s[i]-'0';
        }else if(s[i]=='.'){
            st.push(num);
            num=0;
        }else{
            int x=st.top();
            st.pop();
            int y=st.top();
            st.pop();
            if(s[i]=='+'){
                st.push(x+y);
            }
            if(s[i]=='-'){
                st.push(y-x);
            }
            if(s[i]=='*'){
                st.push(x*y);
            }
            if(s[i]=='/'){
                st.push(y/x);
            }
        }
    }
    cout<<st.top();
    return 0;
}

中缀表达式值(expr)

这道题的大致思路就是先将中缀表达式转化为后缀，在用后缀表达式求出答案。

具体思路

无解

• 括号不匹配，例如：)1+1( (1+3))
• 出现连续多个运算符。

优先级：

右括号>乘除>加减>左括号

中缀转后缀

用一个字符串 suf 来存储后缀表达式，用一个栈 st 来处理中缀转后缀的过程。

• 如果 s_i 为数字，将 s_i 接到 suf 后面。

• 如果 s_i 为 (，直接将左括号入栈。

• 如果 s_i 为 )，直接把这个右括号到最近的左括号之中的所有运算符接到 suf 后面，因为中间的这些运算符比右括号优先级低，所以这些运算符可以直接出栈。

• 如果 s_i 为其他情况(+,-,*,/)，把栈顶的元素不停弹出，直到栈为空或者栈顶元素的优先级小于等于自己，再把自己入栈。

后缀算答案

有了后缀表达式，这道题就和上题一模一样了，后缀算答案直接按上题思路处理即可。

时间复杂度 O(|S|^2)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool is(char c){
    return c=='+'||c=='-'||c=='*'||c=='/';
}
bool check(string s){
    stack<char>st;
    for(auto c:s){
        if(c=='('){
            st.push('(');
        }
        if(c==')'){
            if(st.size()==0){
                return 0;
            }
            st.pop();
        }
    }
    if(st.size()){
        return 0;
    }
    int len=s.size(); 
    for(int i=1;i<len;i++){
        if(is(s[i-1])&&is(s[i])){
            return 0;
        }
    }
    return 1;
}
int prio[205];
stack<char>st;
stack<int>ans;
signed main(){
    string s;
    cin>>s;
    if(check(s)==0){
        cout<<"NO";
        return 0;
    }
    while(s.back()=='@'){
        s.pop_back();
    }
    prio['(']=0;
    prio['+']=1;
    prio['-']=1;
    prio['*']=2;
    prio['/']=2;
    int len=s.size();
    string suf="";
    for(int i=0;i<len;i++){
        if(s[i]>='0'&&s[i]<='9'){
            suf+=s[i];
        }else{
            if(s[i]=='('){
                st.push(s[i]);
            }else if(s[i]==')'){
                while(st.size()>1&&st.top()!='('){
                    suf+=st.top();
                    st.pop();
                }
                st.pop();
            }else{
                while(st.size()&&prio[st.top()]>=prio[s[i]]){
                    suf+=st.top();
                    st.pop();
                }
                st.push(s[i]);
            }
        }
    }
    while(st.size()){
        suf+=st.top();
        st.pop();
    }
    len=suf.size();
    for(int i=0;i<len;i++){
        if(suf[i]>='0'&&suf[i]<='9'){
            ans.push(suf[i]-'0');
        }else{
            if(ans.size()<2){
                continue;
            }
            int x=ans.top();
            ans.pop();
            int y=ans.top();
            ans.pop();
            if(suf[i]=='+'){
                ans.push(x+y);
            }
            if(suf[i]=='-'){
                ans.push(y-x);  
            }
            if(suf[i]=='*'){
                ans.push(x*y);  
            }
            if(suf[i]=='/'){
                ans.push(y/x);  
            }
        }
    }
    cout<<ans.top();
    return 0;
}

表达式的转换

这道题的中最转后缀代码与上一道题基本相似，但是要想输出具体过程就不能按照上一题的代码处理了，因为这道题有删除后缀表达式的一部分和插入后缀表达式的一部分，这种插入和删除操作比较快的就是 vector 了。

• 若 s_i 为数字，不管他。
• 若 s_i 为运算符，把原位删除并替换为运算之后的结果。

然后每一轮都直接输出 vecotr 的元素。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    bool flag;
    int x;
    char c;
};
vector<node>vec;
int cnt=0;
void add(bool flag,int x,char c){
    cnt++;
    vec.push_back({flag,x,c});
    return;
}
int prio[205];
stack<char>st;
int qpow(int x,int y){
    if(y==0){
        return 1;
    }
    if(y==1){
        return x;
    }
    if(y%2==0){
        int t=qpow(x,y/2);
        return t*t;
    }
    return qpow(x,y-1)*x;
}
int main(){
    string s;
    cin>>s;
    prio['(']=0;
    prio['+']=1;
    prio['-']=1;
    prio['*']=2;
    prio['/']=2;
    prio['^']=3;
    prio[')']=4;
    while(s.back()=='@'){
        s.pop_back();
    }
    int len=s.size();
    for(int i=0;i<len;i++){
        if(s[i]>='0'&&s[i]<='9'){
            add(1,s[i]-'0',' ');
        }else{
            if(s[i]=='('){
                st.push(s[i]);
            }else if(s[i]==')'){
                while(st.size()>1&&st.top()!='('){
                    add(0,-1e9,st.top());
                    st.pop();
                }
                st.pop();
            }else if(s[i]=='^'){
                while(st.size()&&prio[st.top()]>prio[s[i]]){
                    add(0,-1e9,st.top());
                    st.pop();
                }
                st.push(s[i]);
            }else{
                while(st.size()&&prio[st.top()]>=prio[s[i]]){
                    add(0,-1e9,st.top());
                    st.pop();
                }
                st.push(s[i]);
            }
        }
    }
    while(st.size()){
        add(0,-1e9,st.top());
        st.pop();
    }
    for(int i=0;i<cnt;i++){
        if(vec[i].flag==0){
            cout<<vec[i].c;
        }else{
            cout<<vec[i].x;
        }
        cout<<" ";
    }
    cout<<"\n";
    for(int i=0;i<cnt;i++){
        if(vec[i].flag==0){
            int x=vec[i-1].x;
            int y=vec[i-2].x;
            char c=vec[i].c;
            int T=3;
            while(T--){
                vec.erase(vec.begin()+i-2);
            }
            if(c=='+'){
                vec.insert(vec.begin()+i-2,{1,x+y,' '});
            }
            if(c=='-'){
                vec.insert(vec.begin()+i-2,{1,y-x,' '});
            }
            if(c=='*'){
                vec.insert(vec.begin()+i-2,{1,x*y,' '});
            }
            if(c=='/'){
                vec.insert(vec.begin()+i-2,{1,y/x,' '});
            }
            if(c=='^'){
                vec.insert(vec.begin()+i-2,{1,qpow(y,x),' '});
            }
            i=0;
            cnt--;
            cnt--;
            for(int j=0;j<cnt;j++){
                if(vec[j].flag==0){
                    cout<<vec[j].c;
                }else{
                    cout<<vec[j].x;
                }
                cout<<" ";
            }
            cout<<"\n";
        }
    }
    return 0;
}