题解 | #给表达式添加运算符+表达式运算校验#

//测试验证程序
public  void Test() {
		String num = "73958";
		int target = 24;
		//73-9-5*8=24
		//73-9-5*8=24
		 String[] res = addOpt(num, target);
		if (res.length==0) {
			System.out.println("NA");
		} else {
			for (String s : res) {
				int n = expressionEvaluation(s);
				System.out.println(s + "=" + n);
			}
		}

	}

public String[] addOpt(String num, int target) {
		List<String> expList = new ArrayList<>();
		helper(target, num, 0, "", 0, expList);
		String[] res = new String[expList.size()];
		int index = 0;
		for (String s : expList) {
			res[index++] = s;
		}
		return res;
	}
    
    /**
	 * 计算目标值
	 * 
	 * @param target       目标值
	 * @param src          源串
	 * @param curResult    子串计算结果
	 * @param exp          当前子串表达式
	 * @param preTmpResult 记录上一次计算结果
	 * @param expList      表达式list
	 */
	public void helper(int target, String src, long curResult, String exp, long preTmpResult, List<String> expList) {
		// 计算完成，并且与目标是相等，将结果点添加到List
		if (curResult == target && src.length() == 0) {
			expList.add(exp);
		}

		int len = src.length();
		for (int i = 1; i <= len; i++) {
			// 1. 将字符串拆分成两个数字，前一个数字，进行计算，针对后面的字符串进行递归
			String firstNumStr = src.substring(0, i);
			long firstNum = Long.parseLong(firstNumStr);
			String splitStr = src.substring(i, len);

			// 如果数字首位是0，则数字为非法数字，直接跳出进入下一次循环
			if (firstNumStr.length() > 1 && firstNumStr.charAt(0) == '0') {
				break;
			}

			// 2. 对分后后，后面的字符串进行递归运算操作，+ - * ÷
			if (exp.length() > 0) {
				helper(target, splitStr, curResult + firstNum, exp + "+" + firstNum, firstNum, expList);
				helper(target, splitStr, curResult - firstNum, exp + "-" + firstNum, firstNum * -1, expList);
				// 乘法存在表达式优先级的问题，要调整curResult的计算方法
				helper(target, splitStr, curResult - preTmpResult + preTmpResult * firstNum, exp + "*" + firstNum,
						preTmpResult * firstNum, expList);
				//除法
				/*helper(target, splitStr, curResult - preTmpResult + preTmpResult / firstNum, exp + "÷" + firstNum,
						preTmpResult / firstNum, expList);*/
			} else {
				// 如果为第一次进入，进行特殊处理
				helper(target, splitStr, firstNum, firstNumStr, firstNum, expList);
			}
		}
	}
    
    
    //表达式添加运算符校验程序
	Map<Character, Integer> map = new HashMap<Character, Integer>() {
		{
			put('-', 1);
			put('+', 1);
			put('*', 2);
			put('/', 2);
			put('%', 2);
			put('^', 3);
		}
	};

	public int expressionEvaluation(String s) {
		// 将所有的空格去掉
		s = s.replaceAll(" ", "");

		char[] cs = s.toCharArray();
		int n = s.length();

		// 存放所有的数字
		Deque<Integer> nums = new ArrayDeque<>();
		// 为了防止第一个数为负数，先往 nums 加个 0
		nums.addLast(0);
		// 存放所有「非数字以外」的操作
		Deque<Character> ops = new ArrayDeque<>();

		for (int i = 0; i < n; i++) {
			char c = cs[i];
			if (c == '(') {
				ops.addLast(c);
			} else if (c == ')') {
				// 计算到最近一个左括号为止
				while (!ops.isEmpty()) {
					if (ops.peekLast() != '(') {
						calc(nums, ops);
					} else {
						ops.pollLast();
						break;
					}
				}
			} else {
				if (isNumber(c)) {
					int u = 0;
					int j = i;
					// 将从 i 位置开始后面的连续数字整体取出，加入 nums
					while (j < n && isNumber(cs[j]))
						u = u * 10 + (cs[j++] - '0');
					nums.addLast(u);
					i = j - 1;
				} else {
					if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
						nums.addLast(0);
					}
					// 有一个新操作要入栈时，先把栈内可以算的都算了
					// 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
					while (!ops.isEmpty() && ops.peekLast() != '(') {
						char prev = ops.peekLast();
						if (map.get(prev) >= map.get(c)) {
							calc(nums, ops);
						} else {
							break;
						}
					}
					ops.addLast(c);
				}
			}
		}
		// 将剩余的计算完
		while (!ops.isEmpty() && ops.peekLast() != '(')
			calc(nums, ops);
		return nums.peekLast();
	}

	// 计算逻辑：从 nums 中取出两个操作数，从 ops 中取出运算符，然后根据运算符进行计算即可
	void calc(Deque<Integer> nums, Deque<Character> ops) {
		if (nums.isEmpty() || nums.size() < 2)
			return;
		if (ops.isEmpty())
			return;
		int b = nums.pollLast(), a = nums.pollLast();
		char op = ops.pollLast();
		int ans = 0;
		if (op == '+')
			ans = a + b;
		else if (op == '-')
			ans = a - b;
		else if (op == '*')
			ans = a * b;
		else if (op == '/')
			ans = a / b;
		else if (op == '^')
			ans = (int) Math.pow(a, b);
		else if (op == '%')
			ans = a % b;
		nums.addLast(ans);
	}

	boolean isNumber(char c) {
		return Character.isDigit(c);
	}