题解 | 24点游戏算法

这道题一开始我尝试将官方解法的源代码放在上面跑，根本就跑不通全部的用例

然后用题解区很多人的源码跑，发现题解的很多源码也根本跑不通所有的测试用例

于是就自己想出了这样一个解法，感觉不是很好，但是终于跑通了2025年更新后的所有测试用例

这代码量都快赶上一个小的项目了，关键是写项目我可以分好几个文件，分好几个包，这就只能在一个文件里面写上几百行

总体思路就是穷举出所有的排列，然后再根据所有的排列穷举所有可能的运算符以及合法的括号设置。为了实现这个功能，我先是用几个回溯搞出了全排列、运算符、和括号位置，得到一堆不重复的公式字符串，然后又自己实现了一个计算器，解析字符串计算出结果，与目标值24进行比较

计算器不考虑运算符优先级，只考虑括号，是可以得出正确结果的，因为在穷举出所有括号位置的时候也将正确的运算符优先级用括号包起来了，计算器解析字符串的逻辑主要用到了栈和二叉树，go这个语言居然连个栈数据结构都没有官方的实现，还要自己写，确实不如java用起来方便。

然后与目标值比较时由于存在除不尽的情况，又想不到用分数来进行表示的方法，所以将无限接近于24的那些float计算结果也都返回true了，例如3 3 8 8这个输入得到的表达式8/(3-(8/3))得到的计算结果是23.999999999999，如果能用分数存储中间计算结果应该是可以得到精确的24的，这里将类似于23.999999999999的结果也视为等于24了，终于跑通了当前所有的用例

package main

import (
	"errors"
	"fmt"
	"strconv"
	"strings"
)

var operators = []string{"+", "-", "*", "/"}

func main() {
	var a, b, c, d int
	_, _ = fmt.Scan(&a, &b, &c, &d)
	permList := getPermutation([]int{a, b, c, d})
	for _, perm := range permList {
		formulas := getAllFormulaStr(perm)
		for _, formula := range formulas {
			calcResult, err := calculateFormula(formula)
			if err != nil {
				continue
			}
			if calcResult == 24 || (calcResult>23.999 && calcResult<24.0001) {
                fmt.Println(true)
                return
            }
		}
	}
	fmt.Println(false)
}

func getPermutation(nums []int) [][]int {
	permList := make([][]int, 0)
	recorded := make(map[string]bool)
	permutationHelper(nums, 0, &permList, recorded)
	return permList
}

func permutationHelper(nums []int, from int, permList *[][]int, recorded map[string]bool) {
	if from == len(nums)-1 {
		numStr := parseToStr(nums)
		if _, ok := recorded[numStr]; ok {
			return
		}
		recorded[numStr] = true
		numsCopy := make([]int, len(nums))
		copy(numsCopy, nums)
		*permList = append(*permList, numsCopy)
		return
	}
	for i := from; i < len(nums); i++ {
		nums[i], nums[from] = nums[from], nums[i]
		permutationHelper(nums, from+1, permList, recorded)
		nums[i], nums[from] = nums[from], nums[i]
	}
}

func parseToStr(nums []int) string {
	str := ""
	for i, num := range nums {
		str += strconv.Itoa(num)
		if i < len(nums) {
			str += ","
		}
	}
	return str
}

func getAllFormulaStr(nums []int) []string {
	results := make([]string, 0)
	//一个排列穷举出所有的运算符和括号，组成一个数组
	//无括号公式
	results = append(results, FormulaWithoutBracket(nums)...)
	//增加括号
	FormulaWithBracket(&results)
	return results
}

func FormulaWithoutBracket(nums []int) []string {
	results := make([]string, 0)
	for _, operator := range operators {
		unFinished := make([]string, 0)
		formulaHelper(nums, 0, operator, &unFinished, &results)
	}
	return results
}

func formulaHelper(nums []int, numIndex int, operator string, unfinishedPart *[]string, finishedPart *[]string) {
	if numIndex >= len(nums) {
		*finishedPart = append(*finishedPart, strings.Join(*unfinishedPart, ""))
		return
	}
	offset := 1
	firstStr := strconv.Itoa(nums[numIndex])
	*unfinishedPart = append(*unfinishedPart, firstStr)
	if numIndex < len(nums)-1 {
		*unfinishedPart = append(*unfinishedPart, operator)
		offset++
	}
	if numIndex < len(nums)-2 {
		for _, nextOp := range operators {
			formulaHelper(nums, numIndex+1, nextOp, unfinishedPart, finishedPart)
		}
	} else {
		formulaHelper(nums, numIndex+1, "", unfinishedPart, finishedPart)
	}
	*unfinishedPart = (*unfinishedPart)[0 : len(*unfinishedPart)-offset]
}

func FormulaWithBracket(srcFormulas *[]string) {
	srcLength := len(*srcFormulas)
	destFormulas := make([]string, 0)
	for i := 0; i < srcLength; i++ {
		brkFormulas := make([]string, 0)
		addBracketFormulas((*srcFormulas)[i], &brkFormulas)
		destFormulas = append(destFormulas, brkFormulas...)
	}
	*srcFormulas = destFormulas
}

func addBracketFormulas(formulaStr string, results *[]string) {
	//先将字符串分为 数字切片和符号切片
	numParts := make([]int, 0)
	symbols := make([]byte, 0)
	numStr := ""
	for _, fc := range formulaStr {
		switch byte(fc) {
		case '+', '-', '*', '/':
			if len(numStr) > 0 {
				num, _ := strconv.Atoi(numStr)
				numParts = append(numParts, num)
				numStr = ""
			}
			symbols = append(symbols, byte(fc))
		default:
			numStr += string(fc)
		}
	}
	if len(numStr) > 0 {
		num, _ := strconv.Atoi(numStr)
		numParts = append(numParts, num)
	}
	addBracketToParts(numParts, symbols, 0, 1, results, make(map[int]int), false)
}

func addBracketToParts(numParts []int, symbols []byte, brkLeftSide, brkRightSide int, results *[]string, brkPairs map[int]int, inner bool) {
	if brkLeftSide < 0 {
		return
	}
	if brkLeftSide >= brkRightSide {
		return
	}
	if brkLeftSide == 0 && brkRightSide >= len(numParts)-1 {
		//左括号在开头，有括号在结尾，和不加括号没区别
		return
	}
	if brkRightSide > len(numParts)-1 {
		//左括号不在开头，右括号越界，返回
		return
	}
	if !validateLeftAndRightBracketIndex(brkPairs, brkLeftSide, brkRightSide) {
		//防止括号交叉
		return
	}
	//当前位置增加左右括号转换成字符串放入结果集
	changeBracketCount(brkPairs, -brkLeftSide, 1)
	changeBracketCount(brkPairs, brkRightSide, 1)
	*results = append(*results, buildFormulaStr(numParts, symbols, brkPairs))
	addBracketToParts(numParts, symbols, brkLeftSide-1, brkRightSide, results, brkPairs, true)
	addBracketToParts(numParts, symbols, brkLeftSide, brkRightSide+1, results, brkPairs, true)
	addBracketToParts(numParts, symbols, brkRightSide+1, brkRightSide+2, results, brkPairs, false)
	changeBracketCount(brkPairs, -brkLeftSide, -1)
	changeBracketCount(brkPairs, brkRightSide, -1)
	if inner {
		return
	}
	//当嵌套括号时不执行后续逻辑
	//去掉当前括号的情况下，右不动，左右移
	addBracketToParts(numParts, symbols, brkLeftSide+1, brkRightSide, results, brkPairs, false)
	//去掉当前括号的情况下，左不动，右移
	addBracketToParts(numParts, symbols, brkLeftSide, brkRightSide+1, results, brkPairs, false)

}

func changeBracketCount(brkPairs map[int]int, brkIndex, offset int) {
	brkCnt, ok := brkPairs[brkIndex]
	if !ok {
		brkCnt = 0
	}
	brkCnt += offset
	if brkCnt > 0 {
		brkPairs[brkIndex] = brkCnt
	} else {
		delete(brkPairs, brkIndex)
	}
}

// 校验括号是否会交叉
func validateLeftAndRightBracketIndex(brkPairs map[int]int, left, right int) bool {
	if right == 0 {
		return false
	}
	// 校验left处没有右括号
	if left > 0 {
		if _, ok := brkPairs[left]; ok {
			return false
		}
	}

	// 校验right处没有左括号
	if _, ok := brkPairs[-right]; ok {
		return false
	}
	return true
}

// 构建字符串，brkPairs为括号对信息，左括号<=0，右括号>0，
func buildFormulaStr(numParts []int, symbols []byte, brkPairs map[int]int) string {
	str := ""
	for i, num := range numParts {
		partStr := strconv.Itoa(num)
		brkNum, ok := brkPairs[-i]
		if ok {
			concatBrackets(&partStr, true, brkNum)
		}
		if i > 0 {
			brkNum, ok = brkPairs[i]
			if ok {
				concatBrackets(&partStr, false, brkNum)
			}
		}
		if i < len(numParts)-1 {
			partStr += string(symbols[i])
		}
		str += partStr
	}
	return str
}

func concatBrackets(str *string, isLeft bool, bracketNum int) {
	for i := 0; i < bracketNum; i++ {
		if isLeft {
			*str = "(" + *str
		} else {
			*str = *str + ")"
		}
	}
}

func calculateFormula(formula string) (float64, error) {
	//解析和计算式子
	rootElement := ParseCalculateElement(formula)
	if rootElement == nil {
		return 0, errors.New("no root element")
	}
	return rootElement.Calculate()
}

func ParseCalculateElement(formula string) CalculateElement {
	stack := Stack[CalculateElement]{}
	//连续的右括号数量统计
	continuousRightBrkCnt := 0
	for _, c := range formula {
		var curElement CalculateElement
		bc := byte(c)
		if bc != ')' {
			if continuousRightBrkCnt&1 > 0 && stack.Size() > 1 {
				//连续的右括号数量为奇数，需要多出一次栈，以保证栈顶是正确的运算符元素 这样a op (b op c) op
				//...这个场景在HandleElementStackWhenMetOperator 就可以得到正确的处理
				//但是stack的size==1时不能这么处理，因为只有(a op b) op ... 这种场景是这样的
				stack.Pop()
			}
			continuousRightBrkCnt = 0
		}
		switch bc {
		case '(':
			curElement = NewOperateCalculateElement(' ')
			if !stack.IsEmpty() {
				if lastElement, ok := stack.Peek().(*BinaryOperateCalculateElement); ok {
					lastElement.AddSubElement(curElement, lastElement.UnInitialed())
				}
			}
			stack.Push(curElement)
		case '+', '-', '*', '/':
			HandleElementStackWhenMetOperator(&stack, bc)

		case ')':
			// 需要处理一下 就出栈吧
			// 当 ((a op b) op c) op d
			if !stack.IsEmpty() {
				stack.Pop()
			}
			continuousRightBrkCnt++
		default:
			//数字0～9
			numVal, _ := strconv.ParseFloat(string(c), 64)
			curElement = NewSingleValueElementWithFloat(numVal)
			if !stack.IsEmpty() {
				if lastElement, ok := stack.Peek().(*BinaryOperateCalculateElement); ok {
					//如果栈里面是一个操作符运算元素，需要检查运算符是否完成初始化，
					//未完成运算符初始化就是符号左边的值，已完成就是右边的值
					lastElement.AddSubElement(curElement, lastElement.UnInitialed())
					stack.Push(curElement)
				} else {
					//说明栈里面就是一个数字值,isLeft为甚么都不重要了，但是该元素不需要再入栈
					stack.Peek().AddSubElement(curElement, true)
				}
			} else {
				stack.Push(curElement)
			}
		}
	}
	if stack.IsEmpty() {
		return nil
	}
	for stack.Size() > 1 {
		stack.Pop()
	}
	return stack.Pop()
}

// HandleElementStackWhenMetOperator 有如下几种场景
// op 代表(+,-,*,/)
// a op ...
//
//	这种场景下 栈中只有一个数字元素 将数字元素出栈 new一个操作符元素，设置上操作符再入栈
//
// a op (b op...
// (a op ...
//
//	这两种场景下 栈中有一个数字元素 和一个未设置操作符的操作符运算元素 将数字元素出栈，出栈后的栈顶设置操作符
//
// a op b op ...
// a op b op c op ...
// 这个场景下 栈中有一个数字元素 和一个完整的操作符运算元素，将数字元素和操作符元素都出栈
// new一个操作符运算元素，操作符为当前操作符，
// 左值为刚刚出栈的操作符运算元素
// (a op b) op ...
// 这种场景下栈顶就是一个完整的操作符运算元素，直接将该元素出栈，然后创建一个运算符元素，将刚刚出栈的运算符元素设置为左值
// a op (b op c) op ...
// 这种场景下栈顶是(b op c)这个操作符运算元素，需要找到a op (b op c)这个整体运算元素，并将其作为新创建的运算符元素的左值，这时需要给运算符元素一个parent指针
// (a op (b op c)) op ...
// 这种场景和(a op b) op ...相同
// a op (b op c op ...)
func HandleElementStackWhenMetOperator(stack *Stack[CalculateElement], operator byte) {
	var leftElement CalculateElement
	leftElement = stack.Pop()
	if opElement, ok := leftElement.(*BinaryOperateCalculateElement); ok {
		if opElement.UnInitialed() {
			// a op (b op...
			// (a op ...
			opElement.FinishInitial(operator)
			stack.Push(opElement)
		} else {
			// (a op b) op ...
			//a op (b op c) op ...
			curElement := NewOperateCalculateElement(operator)
			curElement.AddSubElement(opElement, true)
			stack.Push(curElement)
		}
		return
	}
	if stack.IsEmpty() {
		//匹配 a op ...
		curElement := NewOperateCalculateElement(operator)
		curElement.AddSubElement(leftElement, true)
		stack.Push(curElement)
	} else {
		topElement, ok := stack.Peek().(*BinaryOperateCalculateElement)
		if ok {
			if topElement.UnInitialed() {
				//... op (a op ...
				topElement.FinishInitial(operator)
			} else if topElement.Accomplished() {
				// a op b op ...
				leftElement = topElement
				stack.Pop()
				curElement := NewOperateCalculateElement(operator)
				curElement.AddSubElement(leftElement, true)
				stack.Push(curElement)
			}
		}
	}
}

// CalculateElement 运算单元接口
type CalculateElement interface {
	AddSubElement(subElement CalculateElement, isLeft bool)
	Calculate() (float64, error)
}

// BinaryOperateCalculateElement 二元运算符计算单元
type BinaryOperateCalculateElement struct {
	operator     byte
	leftAndRight [2]CalculateElement
	parent       *BinaryOperateCalculateElement
}

func NewOperateCalculateElement(operator byte) *BinaryOperateCalculateElement {
	return &BinaryOperateCalculateElement{
		operator: operator,
	}
}

func (b *BinaryOperateCalculateElement) UnInitialed() bool {
	return b.operator == ' '
}

func (b *BinaryOperateCalculateElement) FinishInitial(operator byte) {
	b.operator = operator
}

func (b *BinaryOperateCalculateElement) AddSubElement(subElement CalculateElement, isLeft bool) {
	var parentOfSub, subOperateElement *BinaryOperateCalculateElement
	var ok bool
	subOperateElement, ok = subElement.(*BinaryOperateCalculateElement)
	if ok {
		parentOfSub = subOperateElement.parent
	}

	if isLeft {
		if parentOfSub != nil {
			parentOfSub.AddSubElement(b, false)
		}
		b.leftAndRight[0] = subElement
	} else {
		b.leftAndRight[1] = subElement
	}
	if subOperateElement != nil {
		subOperateElement.parent = b
	}
}

func (b *BinaryOperateCalculateElement) Accomplished() bool {
	return !b.UnInitialed() && b.leftAndRight[0] != nil && b.leftAndRight[1] != nil
}

func (b *BinaryOperateCalculateElement) Calculate() (float64, error) {
	if b.leftAndRight[0] == nil || b.leftAndRight[1] == nil {
		return 0, errors.New("uncompleted calculate element")
	}
	leftResult, err := b.leftAndRight[0].Calculate()
	if err != nil {
		return 0, err
	}
	rightResult, err := b.leftAndRight[1].Calculate()
	if err != nil {
		return 0, err
	}
	switch b.operator {
	case '+':
		return leftResult + rightResult, nil
	case '-':
		return leftResult - rightResult, nil
	case '*':
		return leftResult * rightResult, nil
	case '/':
		if rightResult == 0 {
			return 0, errors.New("divide 0")
		}
		return leftResult / rightResult, nil
	}
	return 0, errors.New("invalid operator")
}

type SingleValueCalculateElement struct {
	value float64
}

func NewSingleValueElementWithInt(integerVal int) *SingleValueCalculateElement {
	return NewSingleValueElementWithFloat(float64(integerVal))
}

func NewSingleValueElementWithFloat(val float64) *SingleValueCalculateElement {
	return &SingleValueCalculateElement{value: val}
}

func (s *SingleValueCalculateElement) AddSubElement(c CalculateElement, _ bool) {
	if valueEle, ok := c.(*SingleValueCalculateElement); ok {
		s.value = s.value*10 + valueEle.value
	}
}

func (s *SingleValueCalculateElement) Calculate() (float64, error) {
	return s.value, nil
}

type Stack[T any] struct {
	elements []T
	top      int
}

func (s *Stack[T]) IsEmpty() bool {
	return len(s.elements) == 0
}

func (s *Stack[T]) Push(t T) {
	if s.elements == nil {
		s.elements = make([]T, 0)
	}
	s.elements = append(s.elements, t)
	s.top = len(s.elements)
}

func (s *Stack[T]) Peek() T {
	if s.IsEmpty() {
		panic(errors.New("couldn't peek in empty stack"))
	}
	return s.elements[s.top-1]
}

func (s *Stack[T]) Pop() T {
	if s.IsEmpty() {
		panic(errors.New("couldn't pop in empty stack"))
	}
	topElement := s.elements[s.top-1]
	s.elements = s.elements[:s.top-1]
	s.top--
	return topElement
}

func (s *Stack[T]) Size() int {
	return len(s.elements)
}