chartemp;//获取该中缀表达式中的每一个字符并进行相对应的判断
char ch &＃61;infixExpression.charAt(i);switch(ch) {//忽略空格
case &＃39; &＃39;:break;//如果是左括号直接压入栈中
case &＃39;(&＃39;:
characterStack.push(ch);break;//碰到&＃39;&＃43;&＃39; &＃39;-&＃39;&＃xff0c;将栈中的所有运算符全部弹出去&＃xff0c;直至碰到左括号为止&＃xff0c;输出到队列中去
case &＃39;&＃43;&＃39;:case &＃39;-&＃39;:while (characterStack.size() !&＃61; 0) {
temp&＃61;characterStack.pop();if (temp &＃61;&＃61; &＃39;(&＃39;) {//如果推出来的那个字符刚好是左括号&＃xff0c;那么就重新将左括号放回栈中&＃xff0c;并终止循环
characterStack.push(&＃39;(&＃39;);break;
}
suffix&＃43;&＃61;temp;
}//没有进入循环说明当前为第一次进入或者前面运算都有括号等情况所导致//将当前符号压入栈中
characterStack.push(ch);
suffix&＃43;&＃61; "#";break;//如果是乘号或者除号&＃xff0c;则弹出栈中所有运算符&＃xff0c;直到碰到加号、减号、左括号为止&＃xff0c;最后将该运算符压入栈中
case &＃39;*&＃39;:case &＃39;÷&＃39;:while (characterStack.size() !&＃61; 0) {
temp&＃61;characterStack.pop();//只有比当前优先级高的或者相等的才会弹出到输出队列&＃xff0c;遇到加减左括号&＃xff0c;直接停止当前循环
if (temp &＃61;&＃61; &＃39;&＃43;&＃39; || temp &＃61;&＃61; &＃39;-&＃39; || temp &＃61;&＃61; &＃39;(&＃39;) {
characterStack.push(temp);break;
}else{
suffix&＃43;&＃61;temp;
}
}//没有进入循环说明当前为第一次进入或者前面运算都有括号等情况所导致//将当前符号压入栈中
characterStack.push(ch);
suffix&＃43;&＃61; "#";break;//如果碰到的是右括号&＃xff0c;则距离栈顶的第一个左括号上面的所有运算符将被弹出栈并抛弃左括号(既不需要将左括号输出到队列中也不需要将右括号压入栈中)
case &＃39;)&＃39;:while (!characterStack.isEmpty()) {
temp&＃61;characterStack.pop();if (temp &＃61;&＃61; &＃39;(&＃39;) {break;
}else{
suffix&＃43;&＃61;temp;
}
}break;//默认情况&＃xff0c;如果读取到的是操作数&＃xff0c;则直接送至输出队列
default:
suffix&＃43;&＃61;ch;break;
}
}//最后如果栈中依然还有运算符的话&＃xff0c;则把剩余运算符一次弹出&＃xff0c;送至输出序列
while (characterStack.size() !&＃61; 0) {
suffix&＃43;&＃61;characterStack.pop();
}returnsuffix;
}
第三部分&＃xff1a;将后缀表达式转化成二叉树&＃xff0c;利用二叉树的优先级&＃xff0c;将同等级的运算数进行排序&＃xff0c;从而把中缀表达式不相同的的式子&＃xff0c;转化成为后缀表达式一样的式子&＃xff0c;便可找出重复的式子&＃xff0c;并剔除掉。
/*** function&＃xff1a;优化策略一(按规则优化二叉树&＃xff0c;使其计算过程中不会出现负数)
*
*&＃64;paramtree
*&＃64;return
*/
publicBinaryTree adjustmentTree(BinaryTree tree) {if (tree !&＃61; null) {
String leftValue&＃61;getTreeValue(tree.getLeftTree());
String rightValue&＃61;getTreeValue(tree.getRightTree());//若右子树的值大于左子树&＃xff0c;则交换子树
if (rightValue.equals("") || leftValue.equals("")) {//表示此时已经递归到叶子了&＃xff0c;直接返回即可
returntree;
}else if (dataOperation.calculateData(rightValue, leftValue, "?").equals("1")) {
tree&＃61;swapChildTree(tree);
}
tree.setLeftTree(adjustmentTree(tree.getLeftTree()));
tree.setRightTree(adjustmentTree(tree.getRightTree()));
}returntree;
}/*** function&＃xff1a;优化策略二(中序遍历二叉树&＃xff0c;转化为符合预定运算顺序的带括号的表达式)
*
*&＃64;paramtree
*&＃64;return
*/
publicString treeToExpression(BinaryTree tree) {
String left&＃61; "";
String right&＃61; "";
String expression&＃61; "";if (tree !&＃61; null) {if (tree.getLeftTree() !&＃61; null && tree.getRightTree() !&＃61; null) {
String leftRoot&＃61;tree.getLeftTree().getRootData();
String rightRoot&＃61;tree.getRightTree().getRootData();if (leftRoot.equals("&＃43;") || leftRoot.equals("-") || leftRoot.equals("*") || leftRoot.equals("÷")) {
left&＃61; "(" &＃43; treeToExpression(tree.getLeftTree()) &＃43; ")";
}else{
left&＃61;treeToExpression(tree.getLeftTree());
}if (rightRoot.equals("&＃43;") || rightRoot.equals("-") || rightRoot.equals("*") || rightRoot.equals("÷")) {
right&＃61; "(" &＃43; treeToExpression(tree.getRightTree()) &＃43; ")";
}else{
right&＃61;treeToExpression(tree.getRightTree());
}
}
expression&＃61; left &＃43; tree.getRootData() &＃43;right;
}returnexpression;
}
5、测试运行
这是题目生成个数100个&＃xff0c;数值范围是10的情况
这是生成题目10000条的情况&＃xff0c;经过大量的测试&＃xff0c;发现。。。。。
京公网安备 11010802041100号