[数据结构与算法]洛谷P1175 表达式的转换（栈的应用）

洛谷 P1175 表达式的转换

链接.
难度：提高+/省选-
标签：模拟，字符串，线性结构，栈

题意：

给定一个中缀表达式，让我们输出转化为后缀表达式后计算的每一步。

题解：

1.将中缀表达式转化为后缀表达式。

2.利用栈，应用后缀表达式的运算法则实现运算。

#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include <cctype>
#include<stack>
#include<queue>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<list>
#define mem(a,n) memset(a,n,sizeof a)
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define SYS system("pause");
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

ll gcd(ll a,ll b){ll d; while(b){ d=b; b=a%b; a=d; } return a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll qpow(ll x, ll y) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans *= x; x *= x; } return ans;}
ll qpow(ll x, ll y, int MOD) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans = ans*x%MOD; x = x*x%MOD; } return ans;}
void exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1;y=0;return; } exgcd(b,a%b,x,y); int temp=y; y=x-(a/b)*y, x=temp; return;}
int downcheck(int l, int r){ while (l < r){ int mid = l + r >> 1; if ("check(mid)") r = mid; else l = mid + 1; } return l;}
int upcheck(int l, int r){ while (l < r){ int mid = l + r + 1 >> 1; if ("check(mid)") l = mid; else r = mid - 1;} return l;}
int doublecheck(int l,int r){ while(r-l>1e-8){ int mid=(l+r)>>1; if("check(mid)") l=mid; else r=mid;} return l; }

const int N = 4e5+10,M=20;
const int inf=0x3f3f3f3f;
const int mod=1e9+7; 
const double pi = acos(-1.0);
int n,t,m,x;
string str[1000];
string res="";

 //这个函数，用于比较运算符号的优先级
int priority(const char& ch) {  
    switch(ch) {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    case '^':
        return 3;
    case '(':
    case ')':
        return 0;
    }
}

//将中缀表达式转化为后缀表达式
string chance(string s){
    stack<char>ch;
    for (int i = 0; i < s.size();i++){
        if(isdigit(s[i])) res += s[i];
        else if(s[i]=='(')  ch.push(s[i]);
        else if(s[i]==')'){
            while(ch.top()!='('){
                res += ch.top();
                ch.pop();
            }
            ch.pop();
        }
        else{
              while (!ch.empty() && priority(ch.top()) >= priority(s[i])){
                  res += ch.top();
                  ch.pop();
            }
            ch.push(s[i]);
        }
    }
    while (!ch.empty())   // 最后如果栈中还有剩余的字符，直接弹出并输出
        res += ch.top(), ch.pop();
    return res;
}

//计算各个运算符
int calcNum(const int& a, const int& b, const int& symbol) {
    switch(symbol) {
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    case '/':
        return a / b;
    case '^':
        return (int)pow(a, b);
    }
}

//计算后缀表达式的计算结果
void calc(const string& s) {
    list<int> st;
     for (int i = 0; i < s.size(); i ++)
        cout << s[i] << ' ';
        cout << endl;    
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i]))  st.push_back(s[i] - '0');
        else {                
            int a, b;  
            a = st.back();
            st.pop_back();
            b = st.back();
            st.pop_back();
            st.push_back(calcNum(b, a, s[i])); 
            for (list<int>::iterator it = st.begin(); it != st.end(); ++it)
                cout << *it << ' ';           
            for (register int j = i + 1; j < s.size(); j ++)
                cout << s[j] << ' ';           
            cout << endl;
        }
    }
}

int main(){
    IOS
    string s;
    cin >> s;
    chance(s);
    calc(res);
    //SYS
    return 0;
}