算式转移

算式转移

题目描述

给出一个仅包含加减乘除四种运算的算式（不含括号），如1+2*3/4，在保持运算符顺序不变的情况下，你可以进行若干次如下操作：
如果交换相邻的两个数，表达式值不变，那么你就可以交换这两个数。
现在你可以进行任意次操作，使得算式的数字序列字典序最小，然后输出结果，数字之间的字典序定义为若a<b，则a的字典序小于b。

输入

第一行包括一个整数n,表示算式的长度，即包含n个数字和n-1个运算符。（1<=n<=100000）。
第二行包括一个含有n个非0整数和n-1个运算符的算式，整数与运算符用空格隔开，运算符包括“+，-，*，/”。整数的绝对值不超过1000.

输出

按要求输出字典序最小的表达式，数字与符号之间用空格隔开。

样例输入

6
3 + 2 + 1 + -4 * -5 + 1

样例输出

1 + 2 + 3 + -5 * -4 + 1

分析：

1、可以考虑使用冒泡排序进行排列。以内在中间运算符号的顺序不变，只有数字的顺序变化，所以可能需要把输入字符串中的数字提取出来，可能有点麻烦。
2、对不同的运算符间关系进行分析：

• ‘-’和‘/’两端的数字顺序不能够颠倒；
• ‘*‘两端的数字可以颠倒，但如果前一个符号为‘/’则不可以；
• ‘+‘两端的数字可以颠倒，但如果后一个符号为‘/’或‘*‘则不可以；
• 满足以上情况且当前符号和后一个符号相同，则可以颠倒。

代码

原文：https://www.cnblogs.com/hellovan/p/11422690.html