题解 | 24点游戏算法

package main

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

var operators = []string{"+", "-", "*", "/"}
var digitRegex = regexp.MustCompile(`\d+`)

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
}

// FormulaInfo 公式信息
type FormulaInfo struct {
	NumParts    []int
	Symbols     []byte
	headSymbol  byte
	results     []string
	left, right *FormulaInfo
}

func (f *FormulaInfo) SplitAndMerge() {
	if len(f.NumParts) == 1 {
		numStr := strconv.Itoa(f.NumParts[0])
		f.results = append(f.results, numStr)
		return
	}
	for i := 1; i < len(f.NumParts); i++ {
		f.executeSplitAndMerge(i)
	}
}

func (f *FormulaInfo) executeSplitAndMerge(i int) {
	f.left = &FormulaInfo{
		NumParts: f.NumParts[0:i],
		Symbols:  f.Symbols[0 : i-1],
		results:  make([]string, 0),
	}

	f.right = &FormulaInfo{
		NumParts:   f.NumParts[i:],
		Symbols:    f.Symbols[i:],
		headSymbol: f.Symbols[i-1],
		results:    make([]string, 0),
	}
	f.left.SplitAndMerge()
	f.right.SplitAndMerge()
	f.results = append(f.results, mergeTwoPartFormula(f.left.results, f.right.results, f.right.headSymbol)...)
}

func mergeTwoPartFormula(leftParts, rightParts []string, op byte) []string {
	if rightParts == nil {
		return leftParts
	}
	if leftParts == nil {
		return rightParts
	}
	resultParts := make([]string, 0)
	for _, left := range leftParts {
		for _, right := range rightParts {
			leftIsDigit, rightIsDigit := digitRegex.ReplaceAllString(left, "") == "", digitRegex.ReplaceAllString(right, "") == ""
			if leftIsDigit && rightIsDigit {
				resultParts = append(resultParts, left+string(op)+right)
				continue
			}

			if !leftIsDigit {
				resultParts = append(resultParts, "("+left+")"+string(op)+right)
			}
			if !rightIsDigit {
				resultParts = append(resultParts, left+string(op)+"("+right+")")
			}
			if !leftIsDigit && !rightIsDigit {
				resultParts = append(resultParts, "("+left+")"+string(op)+"("+right+")")
			}
		}
	}
	return resultParts
}
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)
	}
	formulaInfo := &FormulaInfo{
		NumParts: numParts,
		Symbols:  symbols,
		results:  make([]string, 0),
	}
	formulaInfo.SplitAndMerge()
	*results = append(*results, formulaInfo.results...)
}

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 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)
}