输入：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)
}