「 【华为OD机试真题 Go语言实现】441、符号运算 | 机试真题+思路参考+代码解析（C卷）」2024年7月16日

一、符号解析方法

这个方法不知道能否100%，欢迎大家抽中留言。

package _2024od

import (
	"fmt"
)

type Fraction struct {
	numerator   int
	denominator int
}

type expression struct {
	e      []byte
	offset int
}

func normalizeFraction(f *Fraction) {
	if f.denominator < 0 {
		f.numerator = -f.numerator
		f.denominator = -f.denominator
	}
}

func simplifyFraction(f *Fraction) {
	d := maxCommonDividor(f.numerator, f.denominator)
	f.numerator /= d
	f.denominator /= d
}

func maxCommonDividor(a, b int) int {
	if a < 0 {
		a = -a
	}
	if b < 0 {
		b = -b
	}
	for b != 0 {
		r := a % b
		a = b
		b = r
	}
	return a
}

func addFraction(a, b Fraction) Fraction {
	r := Fraction{
		a.numerator*b.denominator + b.numerator*a.denominator,
		a.denominator * b.denominator,
	}
	simplifyFraction(&r)
	return r
}

func subtractFraction(a, b Fraction) Fraction {
	r := Fraction{
		a.numerator*b.denominator - b.numerator*a.denominator,
		a.denominator * b.denominator,
	}
	simplifyFraction(&r)
	return r
}

func multiplyFraction(a, b Fraction) Fraction {
	r := Fraction{
		a.numerator * b.numerator,
		a.denominator * b.denominator,
	}
	simplifyFraction(&r)
	return r
}

func divideFraction(a, b Fraction) Fraction {
	r := Fraction{
		a.numerator * b.denominator,
		a.denominator * b.numerator,
	}
	simplifyFraction(&r)
	return r
}

func parseExpression(exp *expression) Fraction {
	r := parseTerm(exp)
	for exp.offset < len(exp.e) {
		if exp.e[exp.offset] == 32 {
			exp.offset++
			continue
		}
		op := exp.e[exp.offset]
		if op == '+' || op == '-' {
			exp.offset++
			next := parseTerm(exp)
			if op == '+' {
				r = addFraction(r, next)
			} else {
				r = subtractFraction(r, next)
			}
		} else {
			break
		}
	}
	return r
}

func parseTerm(exp *expression) Fraction {
	r := parseFactor(exp)
	for exp.offset < len(exp.e) {
		if exp.e[exp.offset] == 32 {
			exp.offset++
			continue
		}
		op := exp.e[exp.offset]
		if op == '*' || op == '/' {
			exp.offset++
			next := parseFactor(exp)
			if op == '*' {
				r = multiplyFraction(r, next)
			} else {
				r = divideFraction(r, next)
			}
		} else {
			break
		}
	}
	return r
}

func parseFactor(exp *expression) Fraction {
	for exp.offset < len(exp.e) {
		if exp.e[exp.offset] == 32 {
			exp.offset++
			continue
		} else {
			break
		}
	}
	if exp.e[exp.offset] == '(' {
		exp.offset++
		r := parseExpression(exp)
		exp.offset++
		return r
	} else {
		return parseNumber(exp)
	}
}

func parseNumber(exp *expression) Fraction {
	value := 0
	for exp.offset < len(exp.e) {
		if '0' <= exp.e[exp.offset] && exp.e[exp.offset] <= '9' {
			value = value*10 + int(exp.e[exp.offset]-'0')
			exp.offset++
		} else {
			break
		}
	}
	r := Fraction{value, 1}
	return r
}

func solution441() {
	var exp string
	fmt.Scanf("%d", &exp)
	fraction := parseExpression(&expression{
		[]byte(exp),
		0,
	})
	normalizeFraction(&fraction)
	if fraction.denominator == 0 {
		fmt.Println("Error")
	} else if fraction.denominator == 1 {
		fmt.Println(fraction.numerator)
	} else {
		fmt.Printf("%d/%d\n", fraction.numerator, fraction.denominator)
	}
}

题干测试用例

func Test441(t *testing.T) {
	t.Log(parseExpression(&expression{
		[]byte("1 + 5 * 7 / 8"),
		0,
	}))
	t.Log(parseExpression(&expression{
		[]byte("1 /(0-5)"),
		0,
	}))
	t.Log(parseExpression(&expression{
		[]byte("1 * (3*4/(8-(7+0))"),
		0,
	}))
}

二、中缀/后缀表达式求值解法 

 2024.7.17 更新，新增逆波兰表达式求解方法。未知是否能100%。

type Fraction struct {
	numerator   int
	denominator int
}


func normalizeFraction(f *Fraction) {
	if f.denominator < 0 {
		f.numerator = -f.numerator
		f.denominator = -f.denominator
	}
}

func simplifyFraction(f *Fraction) {
	d := maxCommonDividor(f.numerator, f.denominator)
	f.numerator /= d
	f.denominator /= d
}

func maxCommonDividor(a, b int) int {
	if a < 0 {
		a = -a
	}
	if b < 0 {
		b = -b
	}
	for b != 0 {
		r := a % b
		a = b
		b = r
	}
	return a
}

func addFraction(a, b Fraction) Fraction {
	r := Fraction{
		a.numerator*b.denominator + b.numerator*a.denominator,
		a.denominator * b.denominator,
	}
	simplifyFraction(&r)
	return r
}

func subtractFraction(a, b Fraction) Fraction {
	r := Fraction{
		a.numerator*b.denominator - b.numerator*a.denominator,
		a.denominator * b.denominator,
	}
	simplifyFraction(&r)
	return r
}

func multiplyFraction(a, b Fraction) Fraction {
	r := Fraction{
		a.numerator * b.numerator,
		a.denominator * b.denominator,
	}
	simplifyFraction(&r)
	return r
}

func divideFraction(a, b Fraction) Fraction {
	r := Fraction{
		a.numerator * b.denominator,
		a.denominator * b.numerator,
	}
	simplifyFraction(&r)
	return r
}


func inFix2Suffix(exp []byte) []string {
	stack := make([]byte, 0, len(exp))
	output := make([]string, 0, len(exp))

	num := 0
	for i := 0; i < len(exp); i++ {
		// 遇到'('直接加入符号栈
		if exp[i] == '(' {
			stack = append(stack, exp[i])
			continue
		}
		// 遇到')'; 把符号栈中直到'('的符号出栈，加入output中
		if exp[i] == ')' {
			for len(stack) > 0 && stack[len(stack)-1] != '(' {
				top := stack[len(stack)-1]
				output = append(output, string(top))
				stack = stack[:len(stack)-1]
			}
			// 把'('也弹出
			stack = stack[:len(stack)-1]
			continue
		}
		// 遇到运算符
		// 如果当前运算符的优先级高于或等于栈顶运算符的优先级，将其压入操作符栈。
		if exp[i] == '*' || exp[i] == '/' {
			stack = append(stack, exp[i])
			continue
		}

		// 如果当前运算符的优先级低于栈顶运算符的优先级，则依次弹出操作符栈中的运算符并添加到后缀表达式结果栈中，
		// 直到遇到优先级小于或等于当前运算符的运算符或栈为空。然后将当前运算符压入操作符栈。
		if exp[i] == '+' || exp[i] == '-' {
			if len(stack) > 0 {
				top := stack[len(stack)-1]
				if top == '*' || top == '/' {
					for len(stack) > 0 {
						top := stack[len(stack)-1]
						output = append(output, string(top))
						stack = stack[:len(stack)-1]
					}
				}
			}
			// 当前符号入栈
			stack = append(stack, exp[i])
			continue
		}

		// 读取操作数
		for i < len(exp) && '0' <= exp[i] && exp[i] <= '9' {
			num = num*10 + int(exp[i]-'0')
			i++
		}
		output = append(output, strconv.Itoa(num))
		num = 0
		i--
	}

	// 结束处理：遍历完中缀表达式后，如果操作符栈中还有运算符，则依次弹出并添加到后缀表达式结果栈中。
	for len(stack) > 0 {
		top := stack[len(stack)-1]
		output = append(output, string(top))
		stack = stack[:len(stack)-1]
	}

	return output
}

func evalRPN(rpn []string) Fraction {
	stack := make([]Fraction, 0, len(rpn))
	for _, tok := range rpn {
		switch tok {
		case "*":
			{
				a := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				b := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				r := multiplyFraction(b, a)
				stack = append(stack, r)
				break
			}
		case "/":
			{
				a := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				b := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				r := divideFraction(b, a)
				stack = append(stack, r)
				break
			}
		case "+":
			{
				a := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				b := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				r := addFraction(b, a)
				stack = append(stack, r)
				break
			}
		case "-":
			{
				a := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				b := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				r := subtractFraction(b, a)
				stack = append(stack, r)
				break
			}
		default:
			num, _ := strconv.Atoi(tok)
			r := Fraction{
				num,
				1,
			}
			stack = append(stack, r)
			break
		}
	}
	return stack[len(stack)-1]
}

func evalExp(exp string) Fraction {
	e := []byte(strings.Join(strings.Fields(exp), ""))
	return evalRPN(inFix2Suffix(e))
}

func solution441() {
	var exp string
	fmt.Scanf("%d", &exp)
	fraction := evalExp(exp)
	normalizeFraction(&fraction)
	if fraction.denominator == 0 {
		fmt.Println("Error")
	} else if fraction.denominator == 1 {
		fmt.Println(fraction.numerator)
	} else {
		fmt.Printf("%d/%d\n", fraction.numerator, fraction.denominator)
	}
}

测试用例：

func Test441(t *testing.T) {
	t.Log(evalExp("1 + 5 * 7 / 8"))
	t.Log(evalExp("1 /(0-5)"))
	t.Log(evalExp("1 * (3*4/(8-(7+0) ))"))
}