左括号补全-双栈法

atinyant 2020-01-04 原文

输入：1+2)*33-44)*555-666)))

输出：((1+2)*((33-44)*(555-666)))

代码实现及注释：

package main

import "fmt"

/*
	左括号补全算法
*/

type stackString []string

func (s *stackString) Push(v string) {
	*s = append(*s, v)
}

func (s *stackString) Pop() string {
	l := len(*s)
	if l == 0 {
		return ""
	}
	ret := (*s)[l-1]
	*s = (*s)[:l-1]
	return ret
}

type stackByte []byte

func (s *stackByte) Push(v byte) {
	*s = append(*s, v)
}

func (s *stackByte) Pop() byte {
	l := len(*s)
	if l == 0 {
		return 0
	}
	ret := (*s)[l-1]
	*s = (*s)[:l-1]
	return ret
}

func isDigit(str string, i *int) *string {

	if str[*i] > '0' && str[*i] <= '9' {
		var retBytes []byte
		retBytes = append(retBytes, str[*i])
		for j := *i + 1; j < len(str); j++ {
			if str[j] > '0' && str[j] <= '9' {
				retBytes = append(retBytes, str[j])
			} else {
				*i = j - 1
				ret := string(retBytes)
				return &ret
			}
		}
	}
	return nil
}

func isOpeartor(b byte) bool {
	switch b {
	case '+', '-', '*', '/':
		return true
	default:
		return false
	}
}

func main() {
	str := "1+2)*33-44)*555-666)))"
	dataS := make(stackString, 0)
	opS := make(stackByte, 0)
	for i := 0; i < len(str); i++ {
　　　　　　　　　　// 将数字和运算符入栈
		if ret := isDigit(str, &i); ret != nil {
			dataS.Push(*ret)

		} else if isOpeartor(str[i]) {
			opS.Push(str[i])
		} else {
　　　　　　　　　　// 取出表达式（数字）和运算符，合并，并重新入栈
			d2 := dataS.Pop()
			d1 := dataS.Pop()
			op := opS.Pop()
			exp := "(" + d1 + string(op) + d2 + ")"
			dataS.Push(exp)
		}
	}

	var exp string
	for j := 0; j < len(dataS); j++ {
		exp += dataS[j]
	}

	fmt.Println(exp)
}