中缀表达式转化为前缀、后缀表达式的递归算法

中缀表达式可以被划分为part1、oper、part2
将这三部分按part1、part2、oper的顺序组成新的序列即为后缀表达式
同理也可得前缀表达式

下为part1的分类：

测试数据

1+(2-3/4)*5

输出结果

1234/-5*+

#include<iostream>
#include<string> 
using namespace std; 
bool is_oper_or_num(string s){//判断字符是否为运算符或数字
	char c=s[0];
	if(c=='+' || c=='-' || c=='/' || c=='*' || (c>='0' && c<='9'))return true;
	return false;
}
string RPN(string s){
	//递归到长度为1，则不可分割，返回该字符
	if(s.length()==1 && is_oper_or_num(s))return s;

	//第一个字符为括号则说明第一部分可能不是一个字符，
	//而是括号括起来的表达式
	if(s[0]=='('){
		int time=1,i=1;
		string part1="(";
		while(i>0){//完成第一部分的划分
			if(s[time]=='(')i++;
			else if(s[time]==')')i--;
			part1+=s[time];
			time++;
		}
		
		//第一部分为整个字符串，即表达式被括号包围，
		//则删除两侧的括号，重新计算中间的表达式的值
		if(part1==s){
			string del;
			for(int i=1;i<s.length()-1;i++)del+=s[i];
			return RPN(del);
		}
		//表达式可以被分为两部分（第一部分有括号），以及两部分中间的运算符
		else{
			string part2,oper;
			oper+=s[time];
			for(int i=time+1;i<s.length();i++)part2+=s[i];
			return RPN(part1)+RPN(part2)+oper;
		}
	}
	//表达式可以被分为两部分（第一部分为单个数字），以及两部分中间的运算符
	else{
		string part1,part2,oper;
		part1+=s[0];oper+=s[1];
		for(int i=2;i<s.length();i++)part2+=s[i];
		return RPN(part1)+RPN(part2)+oper;
	}
} 
int main(){
	string s;
	cin>>s;
	cout<<RPN(s)<<endl;
}