A、逆逆波兰式
贡献者程序设计2提交情况4 / 5题目描述
Time limit: 1000 ms Memory limit: 256 MB Standard I/O 仔细学习老师关于“递归”的ppt之后，你学会了如何将一个逆波兰式转换回原本的表达式；只是，有些时候，你会输出大量多余的括号。
这次，我们仍旧要将一个逆波兰式转换回一个正常的表达式—— 但不能输出任何多余的括号 。【警告】可以使用栈，但不允许使用C++的std::stack
【逆逆波兰式】题面中的“多余”说明：https://git.ustc.edu.cn/programming-ii-spring2021/DiscussionBoard/-/issues/15
输入描述
输入有且只有一行，行末回车符前只会出现“+”“-”“*”“/”和数字“0”到“9”；数字至少出现一次，每一个数字代表一个单独的数值（原表达式和逆波兰式中的数都是一位数）。
输出描述
输出包括一行，为输入逆波兰式对应的原表达式，但不能有任何 多余的括号 ！
样例输入
123++样例输出
1+(2+3)样例输入
12+3+样例输出
1+2+3样例输入
12+34+*样例输出
(1+2)*(3+4)
我们平时所使用的式子为中辍表达式，而逆波兰表达式也是后辍表达式，通过把运算符后置来实现括号等形式的简化。同理，波兰表达式是前辍表达式，我们在这里只讨论逆波兰表达式。
通过递归程序及优先级参数来确定所对应的中辍表达式以及括号的有无。
在这里，我们通过构造exchange函数来实现这个功能。
string exchange(string str, int order)//str为输入字符串，order为优先级参数
{
while ( l-- && l >= 0)//l为字符串长度，此句为递归终止条件判定
{
if (str[l] == ‘+‘)
{
if (order <= 0)
return exchange(str, 0) + ‘+‘ + exchange(str, 1);
else
return ‘(‘ + exchange(str, 0) + ‘+‘ + exchange(str, 1) + ‘)‘;
}
else if (str[l] == ‘-‘)
{
if (order <= 0)
return exchange(str, 0) + ‘-‘ + exchange(str, 1);
else
return ‘(‘ + exchange(str, 0) + ‘-‘ + exchange(str, 1) + ‘)‘;
}
else if (str[l] == ‘*‘)
{
if (order <= 1)
return exchange(str, 1) + ‘*‘ + exchange(str, 2);
else
return ‘(‘ + exchange(str, 1) + ‘*‘ + exchange(str, 2) + ‘)‘;
}
else if (str[l] == ‘/‘)
{
if (order <= 1)
return exchange(str, 1) + ‘/‘ + exchange(str, 2);
else
return ‘(‘ + exchange(str, 1) + ‘/‘ + exchange(str, 2) + ‘)‘;
}
else
{
string s;
s.push_back(str[l]);
return s;
}
}
同上一样，通过构造exchange函数，不过此方法多使用char型字符数组和结构体进行操作，灵感来源于他人。
此处构造结构体来实现对输入字符串，输出字符串的统一。
typedef struct
{
char str1[MAX_LENGTH];
char sign[MAX_NUM];
char str2[MAX_LENGTH];
} TREE;
然后......比较复杂，先贴代码，读者可自行理解，后续补充思路
void exchange()
{
int i = 0;
char a[100], temp[100];
scanf("%s", a);
for (i = 0; a[i] != ‘\0‘; i++)
{
switch (a[i])
{
case ‘+‘:
case‘-‘:
//If only the first member of the penultimate structure stores information,
//there is no need to push the information of the other two members into
if (list[num - 2].sign[0] != ‘\0‘)
{
strcpy(temp, list[num - 2].str1);
strcat(list[num - 2].str1, list[num - 2].sign);
strcat(list[num - 2].str1, list[num - 2].str2);
}
list[num - 2].sign[0] = a[i];//Add operator
if (list[num - 1].sign[0] != ‘\0‘)
{
if (list[num - 1].sign[0] == ‘*‘ || list[num - 1].sign[0] == ‘/‘)
{
strcpy(list[num - 2].str2, list[num - 1].str1);
strcat(list[num - 2].str2, list[num - 1].sign);
strcat(list[num - 2].str2, list[num - 1].str2);
}
else
{
////Add parentheses to ensure priority
strcpy(list[num - 2].str2, "(");
strcat(list[num - 2].str2, list[num - 1].str1);
strcat(list[num - 2].str2, list[num - 1].sign);
strcat(list[num - 2].str2, list[num - 1].str2);
strcat(list[num - 2].str2, ")");
}
}
else
{
strcpy(list[num - 2].str2, list[num - 1].str1);
}
memset(&list[num - 1], 0, sizeof(TREE));
num--;
break;
case ‘/‘:
case ‘*‘:
//If only the first member of the penultimate structure stores information,
//there is no need to push the information of the other two members into
if (list[num - 2].sign[0] != ‘\0‘)
{
if (list[num - 2].sign[0] == ‘*‘ || list[num - 2].sign[0] == ‘/‘)
{
strcat(list[num - 2].str1, list[num - 2].sign);
strcat(list[num - 2].str1, list[num - 2].str2);
}
else//Add parentheses to ensure priority
{
strcpy(temp, list[num - 2].str1);
strcpy(list[num - 2].str1, "(");
strcat(list[num - 2].str1, temp);
strcat(list[num - 2].str1, list[num - 2].sign);
strcat(list[num - 2].str1, list[num - 2].str2);
strcat(list[num - 2].str1, ")");
}
}
list[num - 2].sign[0] = a[i];
if (list[num - 1].sign[0] != ‘\0‘)
{
//Add parentheses to ensure priority
strcpy(list[num - 2].str2, "(");
strcat(list[num - 2].str2, list[num - 1].str1);
strcat(list[num - 2].str2, list[num - 1].sign);
strcat(list[num - 2].str2, list[num - 1].str2);
strcat(list[num - 2].str2, ")");
}
else
{
strcpy(list[num - 2].str2, list[num - 1].str1);
}
//Clear the variable information of the first to last structure
memset(&list[num - 1], 0, sizeof(TREE));
num--;
break;
default:
list[num].str1[0] = a[i];
list[num].str1[1] = ‘\0‘;
num++;
break;
}
}
//All information is pushed into the first structure member
printf("%s", list[0].str1);
if (list[0].sign[0] != ‘\0‘)
{
printf("%c", list[0].sign[0]);
}
printf("%s", list[0].str2);
}
如有其他思路及更好理解，欢迎与我沟通交流。
原文：https://www.cnblogs.com/zzx6869/p/14652131.html