7-20 表达式转换(栈)[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}