借助栈来实现单链表的逆置运算_中缀后缀表达式转换

全栈程序员-站长 • 2022年8月8日下午9:00 • 未分类 • 阅读 6

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

原题链接
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。

输出格式:
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

输入样例:

2+3*(7-4)+8/4

输出样例:

2 3 7 4 - * + 8 4 / +

注意
数字前面有正负号和小数的情况

#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
typedef struct Node * pnode;
    string line;
char isSignal(int u){ 
   
    if((line[u] == '+' && !(u - 1 == -1 || line[u -1] == '(' || line[u - 1] == '+' || line[u - 1] == '-'||line[u - 1] == '*'||line[u - 1] == '/'))  //此+号是运算符
       ||(line[u] == '-' && !(u - 1 == -1 || line[u -1] == '(' || line[u - 1] == '+' || line[u - 1] == '-'||line[u - 1] == '*'||line[u - 1] == '/'))    //此-号是运算符
       || line[u] == '/' || line[u] == '*' || line[u] == '(' || line[u] == ')')return true;
    else return false;
}
string getNum(int &u){ 
   
    bool flag = false;
    if(line[u] == '-' || line[u] == '+'){ 
   
        if(line[u] == '-')flag = true;
        u ++;
    }
    int i = u;
    while(isalnum(line[u]) || line[u] == '.')
        u ++;
    string re = "";
    if(flag)re = "-";
    re +=line.substr(i,u - i);
    return re;
}
int main(){ 
   
    getline(cin,line);
    int i = 0;
    string num;
    vector<string> res;
    stack<char>s;
    stringstream word;
    string x;
    while(i < line.size()){ 
   
        word.clear();
        if(isSignal(i)){ 
   
            if(line[i] == '*' || line[i] == '/'){ 
   
                s.push(line[i]);
            }
            else if(line[i] == '+' || line[i] == '-'){ 
   
                while(!s.empty() && (s.top() == '/' || s.top() == '*'|| s.top() == '+' || s.top() == '-')){ 
   
                    word.clear();
                    word << s.top();
                    word >> x;
                    res.push_back(x);
                    s.pop();
                }
                s.push(line[i]);
            }
            else if(line[i] == '('){ 
   
                s.push(line[i]);
            }else if(line[i] == ')'){ 
   
                while(!s.empty() && s.top() != '('){ 
   
                    word.clear();
                    word << s.top();
                    word >> x;
                    res.push_back(x);
                    s.pop();
                }
                if(s.top() == '(')s.pop();
            }
            i ++;
        }else { 
   
            num = getNum(i);
            word << num;
            word >> x;
            res.push_back(x);
        }
    }
    while(!s.empty()){ 
   
        word.clear();
        word << s.top();
        word >> x;
        res.push_back(x);
        s.pop();
    }
    cout<<res[0];
    for(int i = 1;i < res.size();i ++)
       cout<<" "<<res[i];

    return 0;
}