实现根据带小括号的算式获得计算结果的静态方法 ——栈空间的特点、递归的使用-一一网

引言

最近在看韩顺平老师的数据结构：栈空间实现综合计算器，前面实现不带小括号的计算器的思路，韩老师已给出：通过数栈和运算符栈来对算式进行处理…。对于后续对计算器的优化，韩老师提出的思路是通过将中缀表达式转成后缀表达式来完成的。而我想到了一种新的思路：不将中缀表达式转成后缀表达式，将每个括号内的算式作为原算式仅通过递归的方式实现。

思路分析

以一个简单的多层嵌套的算式为例：((2+1)+((2+1)+12))*2+40，这个算式中包含了两种情况：

括号的嵌套： ((2+1)+12)，其中2+1是((2+1)+12)的子算式
一个算式内出现多个带括号的子算式，如((2+1)+((2+1)+12))中的2+1和(2+1)+12被同一个括号括起来。

先计算被嵌套在最里面的且自身不嵌套括号的子算式，然后将算式替换为该子算式的计算结果，这样将得到一个新的总算式，然后再继续计算里面的子算式…。实际步骤如下：

((2+1)+((2+1)+12))*2+40中的2+1是一个不带括号的子算式，计算得到2+1 = 3,将计算结果3替换2+1,得到新的算式(3+((2+1)+12))*2+40
(3+((2+1)+12))*2+40中的2+1是一个不带括号的子算式，将计算结果2+1 = 3替换,得到新的算式(3+(3+12))*2+40
…省略一些步骤…

最后得到算式 18*2+40,这是一个不带括号的算式，直接将算式输入到不能识别小括号的计算器中，输出得到最终结果

注解：子算式指的是一个算式中带小括号的部分，子算式是多层级的关系：
如2+1、(2+1)+12是 ((2+1)+((2+1)+12))的子算式，2+1是((2+1)+12)的子算式。
复制代码

方式的功能介绍

calculateFormula(String formula) ：不能识别小括号的计算器，输入不带小括号的算式，返回结果
calculateAnyFormala(String formula) ：能识别小括号的计算器，支持输入带小括号的算式，返回结果

完整代码

        //支持带小括号的计算器
	public static int calculateAnyFormala(String formula) {
		if (formula.contains("(") || formula.contains(")")) {
			// 1、获得第一个'(;的索引，最后一个')'的索引 获取下一个'('和')'
			/*
			 * 分析:如果下一个括号是')'则截取位置为：frist+1 ~ nextr ，如果下一个括号是'('则截取位置为：frist+1 ~ last
			 */
			int frist = formula.indexOf("(");
			int nextr = formula.indexOf(")", frist + 1);
			int nextl = formula.indexOf("(", frist + 1);
			int last = formula.lastIndexOf(")");

			// 创建子字符串，用以获得子算式
			String subStr = "";
			if (nextl == -1 || nextl < nextr) {
				subStr = formula.substring(frist + 1, last);
			} else {
				subStr = formula.substring(frist + 1, nextr);
			}

			// 递归，将子算式代入此函数，将得到的结果返回，从而得到新的算式
			int result = calculateAnyFormala(subStr);
			StringBuilder sb = new StringBuilder("(");
			sb.append(subStr);
			sb.append(")");
			formula = formula.replace(sb.toString(), String.valueOf(result));
			return calculateAnyFormala(formula);
		} else {
			return calculateFormula(formula);
		}
	}
复制代码

// 不能带小括号的计算器
	public static int calculateFormula(String formula) {
		// 直接转成数组，先不考虑公式中有其他无关字符的情况，且公式输入无误
		char[] charArray = formula.toCharArray();

		// 初始化数字栈和字符栈的内存空间
		numStack = new ArrayStack(charArray.length);
		operatorStack = new ArrayStack(charArray.length);

		// 遍历式子的数组，按照运算规则分别向数字栈和字符栈添加数据
		/*
		 * 1、需要判断是运算符还是数字 2、如果是数字就直接入栈 3、如果是运算符就要分情况： 3.1第一个就直接入栈
		 * 3.2如果不是第一个就跟栈顶的运算符比较优先级 , 如果优先级小于等于上一个运算符，则上一个运算符可能是乘除法，需要马上计算
		 * 需要注意的是：ArrayStack只能存放int类型的数据，故调用getOperator方法是需要对数据进行强转
		 */
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < charArray.length; i++) {
			Operator element = Operator.getOperator(charArray[i]);

			if (element == null) {
				sb.append(charArray[i]);
			} else {
				// 数字直接入栈
				numStack.push(Integer.parseInt(sb.toString()));
				sb = new StringBuilder();

				// 对运算符进行判断
				if ((!operatorStack.isEmpty())
						|| element.level > Operator.getOperator((char) operatorStack.topElement()).level) {
					operatorStack.push(charArray[i]);
				} else {
					int firstNum = numStack.pop();
					int secondNum = numStack.pop();
					// 计算临时结果
					int tempResult = calculateTwoNum(secondNum, firstNum,
							Operator.getOperator((char) operatorStack.pop()));
					// 新入栈
					numStack.push(tempResult);
					operatorStack.push(charArray[i]);
				}
			}
		}
		// 最后可能的情况 a+b ; a+b*c 不是以数字结束 a+b+ -> c+ ; a+d*
		numStack.push(Integer.parseInt(sb.toString()));
		int count = operatorStack.getTop();
		for (int i = 0; i <= count; i++) {
			int firstNum = numStack.pop();
			int secondNum = numStack.pop();
			int tempResult = calculateTwoNum(secondNum, firstNum, Operator.getOperator((char) operatorStack.pop()));
			numStack.push(tempResult);
		}
		return numStack.pop();
	}
复制代码