The introduction

Recently at the teacher han Shunping’s data structure: stack space to achieve a comprehensive calculator, the front of the realization of the idea of a calculator without parentheses, Han teacher has given: through the number stack and operator stack to deal with the formula… . For the subsequent optimization of the calculator, Han proposed the idea is to change the infix expression into a suffix expression to complete. However, I came up with a new idea: instead of changing the infix expression into the suffix expression, the formula in each parenthesis is regarded as the original formula only by recursion.

Thought analysis

Take a simple nested multi-layer algorithm: (2+1)+((2+1)+12))*2+40. This algorithm contains two cases:

  1. Nesting of parentheses:((2 + 1) + 12), including2 + 1is((2 + 1) + 12)theThe child formula
  2. A formulaMultiple parentheses are present inThe child formula, such as((2 + 1) + (2 + 1) + (12))In the2 + 1andThe (2 + 1) + 12It’s in the same bracket.

First compute the nested subexpression without nested parentheses, then replace the subexpression with the result of that subexpression, so as to obtain a new general expression, and then continue to compute the subexpression inside… . The actual steps are as follows:

  1. ((2 + 1) + (2 + 1) + (12)) * 2 + 2 + 1 is one of 40 children formula without parentheses, 2 + 1 = 3 is calculated, the calculated results of 3 replace 2 + 1, get the new formula (3 + (2 + 1) + (12)) * 2 + 40

  2. (3 + (2 + 1) + (12)) * 2 + 2 + 1 is one of 40 children without parentheses formula, the calculated results 2 + 1 = 3 replacement, get new formula (3 + (3 +)) * 2 + 40

  3. . Skip some steps…

The result is 18*2+40, which is an expression without parentheses. The expression is typed directly into a calculator that does not recognize parentheses, and the output is the final result

Note: a subroutine is the bracketed part of an expression. A subroutine is a multilevel relation: e.g2+1, (2+1) +12Is ((2+1A) + ((2+1) +12)),2+1Is ((2+1) +12).Copy the code

The function of the

  1. calculateFormula(String formula) ：Calculator that does not recognize parentheses, enter an expression without parentheses, and return the result
  2. calculateAnyFormala(String formula) ：A calculator that recognizes parentheses, supports the input of parentheses and returns the result

The complete code

        // Support calculator with parentheses
	public static int calculateAnyFormala(String formula) {
		if (formula.contains("(") || formula.contains(")")) {
			// get the first '(; The index of the last ')' gets the next '(' and ')'
			/* * analysis: if the next parenthesis is ')', the intercept position is: frist+1 ~ nextr, if the next parenthesis is '(', the intercept position is: frist+1 ~ last */
			int frist = formula.indexOf("(");
			int nextr = formula.indexOf(")", frist + 1);
			int nextl = formula.indexOf("(", frist + 1);
			int last = formula.lastIndexOf(")");

			// Create a substring to get the subalgorithm
			String subStr = "";
			if (nextl == -1 || nextl < nextr) {
				subStr = formula.substring(frist + 1, last);
			} else {
				subStr = formula.substring(frist + 1, nextr);
			}

			// Return the result of this function, so as to get a new formula
			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 {
			returncalculateFormula(formula); }}Copy the code
// no calculator with parentheses
	public static int calculateFormula(String formula) {
		// Convert to array, regardless of other irrelevant characters in the formula, and the formula input is correct
		char[] charArray = formula.toCharArray();

		// Initializes the memory space of the numeric stack and character stack
		numStack = new ArrayStack(charArray.length);
		operatorStack = new ArrayStack(charArray.length);

		// Add data to numeric stack and character stack respectively according to the operation rules
		/* * 1; /* * 1; /* * 2; If the priority is less than or equal to the previous operator, then the previous operator may be multiplication and division, which needs to be calculated immediately * note: ArrayStack can store only int data, so calling getOperator requires a strong */
		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 {
				// The number is pushed directly into the stack
				numStack.push(Integer.parseInt(sb.toString()));
				sb = new StringBuilder();

				// Judge the operator
				if((! operatorStack.isEmpty()) || element.level > Operator.getOperator((char) operatorStack.topElement()).level) {
					operatorStack.push(charArray[i]);
				} else {
					int firstNum = numStack.pop();
					int secondNum = numStack.pop();
					// Calculate the provisional result
					int tempResult = calculateTwoNum(secondNum, firstNum,
							Operator.getOperator((char) operatorStack.pop()));
					/ / the new stacknumStack.push(tempResult); operatorStack.push(charArray[i]); }}}// The last possible case is a+b; A +b*c does not end with a number 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();
	}
Copy the code

Link to data structure course by Han Shunping

www.bilibili.com/video/BV1E4…