C++题目_中缀表达式转后缀表达式(常考)

时间限制: 1.0 Sec  内存限制: 128 MB

题目描述

给定一个中缀表达式，请你输出其对应的后缀表达式

输入

输入一行字符串 s （|s| ≤ 100）表示一个合法的中缀表达式，且其中的数字都在INT范围内，同时也保证只会出现 +，-，*，/, (，) 这几种符号。

输出

输出一行，表示该中缀表达式所对应的后缀表达式，中间用空格隔开。

样例输入1         复制

9+(3-11)*3+8/2 

样例输出1         复制

9 3 11 - 3 * + 8 2 / +

题目链接：hat8.zemeitong.cn/askai/1002?channel=bdtoufangztAskHD5

代码：

#include<bits/stdc++.h> using namespace std; string s; stack<char> st; int main() {     cin>>s;     map<char, int>mp = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};     for(int i = 0; i < s.length(); i ++)     {         if(isdigit(s[i]))         {             int j = i;             int val = 0;             while(j < s.length() && isdigit(s[j]))             {                 val = val * 10 + s[j] - '0';                 j ++;             }             i = j - 1;             cout<<val<<" ";         }         else         {             if(s[i] == '(')             {                 st.push('(');             }             else if(s[i] == ')')             {                 while(st.top() != '(')                 {                     cout<<st.top()<<" ";                     st.pop();                 }                 st.pop();             }             else             {                 while(st.size() > 0 && st.top() != '(' && mp[st.top()] >= mp[s[i]])                 {                     cout<<st.top()<<" ";                     st.pop();                 }                 st.push(s[i]);             }         }     }     while(st.size())     {         cout<<st.top()<<" ";         st.pop();     }     return 0; }