栈的运用

展开括号中字符串

就是有数字有字母,括号,要求按括号展开字符串,并且匹配相应模式

/*
2(A2(AN)) 可以转成 AANAN AANAN
利用栈的知识 设置一个数字栈和字符串栈
每次没遇到左右括号 就拼接数字或者字符串
如果遇到左括号,就入栈数字和字符串
如果遇到右括号,就出栈数字和字符串进行组合,并且加到目前字符串栈顶后面
*/
string parse(const string& s) {
    stack<int> numStk;
    stack<string> strStk;
    string res;
    int num = 0;
    for (char c : s) {
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
        } else if (c == '(') {
            numStk.push(num);
            num = 0;
            strStk.push(res);
            res = "";
        } else if (c == ')') {
            string temp = res;
            for (int i = 0; i < numStk.top() - 1; ++i) {
                res += temp;
            }
            res = strStk.top() + res;
            strStk.pop();
            numStk.pop();
        } else {
            res += c;
        }
    }
    return res;
}

# py版本感觉更简洁 多学学
def parse(s):
    num_stack = []
    str_stack = []
    res = ""
    num = 0
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c == '(':
            num_stack.append(num)
            num = 0
            str_stack.append(res)
            res = ""
        elif c == ')':
            temp = res
            for _ in range(num_stack.pop() - 1):
                res += temp
            res = str_stack.pop() + res
        else:
            res += c
    return res

求后缀表达式

洛谷P14449

就是根据后缀表达式来求出最后的结果,无需转换,计算机最喜欢后缀表达式了

#include<bits/stdc++.h>
using namespace std;

int todig(string s)
{
    int t = 0;
    for(auto i : s)
    {
        t = (i - '0') + t* 10;
    }
    return t;
}
int main()
{
    string s;cin >> s;
    
    map<char,int>mp;
    mp['.'] = 1;
    mp['+'] = 2;
    mp['-'] = 3;
    mp['*'] = 4;
    mp['/'] = 5;
    stack <int> st;
    string num = "";
    for(auto i : s)
    {
        if(mp[i]==1)//主动结束
        {
            int t = todig(num);
            num = "";
            st.push(t);
        }else if(mp[i]>1)
        {
            int a = st.top();
            st.pop();
            int b = st.top();
            st.pop();
            if(i=='+') st.push(a+b);
            if(i=='-') st.push(b-a);
            if(i=='*') st.push(b*a);
            if(i=='/') st.push(b/a);
        }else{
            num+=i;
        }
    }
    cout << st.top();
    return 0;
}

中缀表达式

洛谷P1175

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
map<char,int>mp;
string s;
// 用两种方法实现中缀表达式求值
// 1.先求出中缀转后缀 然后求解后缀表达式
// 2.直接对中缀表达式进行解析 求出结果

string fun1()
{
    // 优先级大的可以累加在后面
    vector <char> vi;
    string vs;
    stack <char> st;
    for(auto i : s)
    {
        if(mp[i]>=2 && mp[i]<=4)//不为数字 且不为左右括号
        {
            if(st.empty())//为空 直接放置
            {
                st.push(i);
            }else{
                //取出栈顶 比较优先级
                while(mp[st.top()] >= mp[i])
                {
                    // cout << mp[st.top()]  <<" " << mp[i]<<"\n";
                    vs+=st.top();
                    st.pop();
                    if(st.empty()) 
                    {
                        // cout <<"6666";
                        break;
                    }
                }
                //  cout << mp[st.top()]  <<" " << mp[i]<<"\n";
                
                st.push(i);
            }
            
            
        }else if(mp[i]==1)//左括号
        {
            st.push(i);
        }else if(mp[i]==5)//右括号 需要取出该括号所有元素
        {
            while(mp[st.top()]!=1)//直到识别左括号
            {
                if(mp[i]!=1)
                vs+=st.top();
                st.pop();
            }
            //  cout << mp[st.top()]  <<" " << mp[i]<<"\n";
            st.pop();
        }
        else{
            vs+=i;
        }
    }
    while(!st.empty())
    {
        if(st.top()!='(')
        vs+=st.top();
        st.pop();
    }
    // cout << vs;
    return vs;
}

void ct(string vs)
{
    // queue<int>q;
    // cout << vs <<"\n";
    for(auto i : vs) cout << i << " ";
    cout <<"\n";
    vector<int>vi;
    for(int i = 0;i<vs.size();i++)
    {
        
        // cout << vs[i]<<"\n";
        if(vs[i]>='0' && vs[i]<='9')
        {
            vi.push_back(vs[i] -'0');//放入数字
        }else{
            int a = vi.back();
            vi.pop_back();
            int b = vi.back();
            vi.pop_back();
            char op = vs[i];// 操作数
            if(op=='+') vi.push_back(a+b);
            else if(op=='-') vi.push_back(b-a);
            else if (op=='*') vi.push_back(b*a);
            else if(op=='/') vi.push_back(b/a);
            else if(op=='^') vi.push_back(pow(b,a));
            
            for(auto n : vi) cout << n <<" ";
            for(int j = i +1;j<vs.size();j++) cout << vs[j]<<" ";
            cout << "\n";
            // return ;
        }
    }
}

int main()
{
    cin >> s;

    // 表示优先级
    mp['('] = 1;
    mp['^'] = 4;
    mp['+'] = 2;
    mp['-'] = 2;
    mp['*'] = 3;
    mp['/'] = 3;
    mp[')'] = 5;
    // cout << fun1();
    ct(fun1());
    return 0;
}
/*
8-(3+2*6)/5+4

8 3 2 6 * + 5 / - 4 + 
8 3 12 + 5 / - 4 + 
8 15 5 / - 4 + 
8 3 - 4 + 
5 4 + 
9
*/

题目要求算出后缀表达式,并且一步步的求解最后的结果,具体里面的分析就是先判断优先级,需要处理括号的两个特殊情况,还有里面因为变量名的问题,导致出来了好几个问题,特别是vs和s的处理

用栈来模拟递归

#include<bits/stdc++.h>
using namespace std;
// 利用栈来实现递归操作

int dfs(int x)
{
    if(x<10) return x*10 + x;
    int a = dfs(x/10);
    int b = dfs(x%10);
    return a*100+b;
}
/*
主要每次将第一次求出的值放进栈中
例如 1234 123 12 1
然后取出每次入栈的元素,再加上右支即可
*/
int stdfs(int x)
{
    stack <int>st;
    while(x!=0)
    {
        st.push(x);
        x/=10;
    }
    int sum = 0;
    while(!st.empty()){
        int top = st.top();
        st.pop();
        if(top>10){
            sum = sum*100 + (top%10)*11;
        }else {
            sum = top*11;
        }
    }
    return sum;
}

int main()
{
    int n;cin >> n;
    cout << dfs(n)<<"\n";
    cout << stdfs(n);
    return 0;
}

处理这类问题的基本方法就是,先将需要求的,也就是每次递归调用的参数放入栈中,然后分别取出栈内的元素,再做具体的操作,乘法或者相加之类的操作,就是按照先后顺序