go - 在golang中的表达式中检查括号是否平衡[保持]

Question

给定表达式字符串exp，编写程序检查exp中“{”、“}”、“（”、“）”、“[”、“]的对和顺序是否正确。

package main

import (
    "fmt"
    stack "github.com/golang-collections/collections/stack"
)
func main() {

    s:= "(a[0]+b[2c[6]])){24+53}"
    stackO  := stack.New()


    stackmap  := map[string]string{"[": "]", "(": ")", "{" : "}"}

    var str = ""
     for _, num := range s{

        str = string(num)

        if(str == "{" || str ==  "[" || str ==  "(" ){
            stackO.Push(str )
        }
        if(str == "}" || str ==  "]" || str ==  ")" ){

            ot := stackO.Peek()
            if(ot == nil){
            fmt.Println("Not balanced" , str )
                break
            }
            closing := stackmap[ot.(string)]
            fmt.Println(closing , str)
            if(closing != str ){
                fmt.Println("Not balanced" , str )
                break
            }else{
            stackO.Pop()
            }


            }
        }


}

Answer 1

我的拿来
main.go

package main

import (
    "bytes"
    "fmt"

    stack "github.com/golang-collections/collections/stack"
)

func main() {
    s := "(a[0]+b[2c[6]])){24+53}"
    fmt.Println("balance1", balance1(s))
    var chars = "[]{}()"
    var brackets = map[byte]byte{'[': ']', '(': ')', '{': '}'}
    fmt.Println("balance2", balance2([]byte(s), brackets, []byte(chars)))
}

func balance2(input []byte, brackets map[byte]byte, chars []byte) error {

    var start int
    // stack := make([]byte, 0, 10)
    stack := input[len(input):]
    stack = stack[:0]
    var c byte
    var opposite byte

    var i int
    for start < len(input) {
        i = bytes.IndexByte(input[start:], opposite)
        if i == -1 {
            for _, char := range chars {
                if char == opposite {
                    continue
                }
                if e := bytes.IndexByte(input[start:], char); e > -1 && (e < i || i == -1) {
                    i = e
                }
            }
            if i == -1 {
                break
            }
        }
        c = input[start+i]
        start += i + 1
        if x, ok := brackets[c]; ok {
            stack = append(stack, c)
            opposite = x
        } else if slen := len(stack); slen > 0 && opposite == c {
            stack = stack[:slen-1]
            if slen > 1 {
                opposite = brackets[stack[slen-2]]
            }
        } else {
            return unbalancedErr{c: c, at: start - 1}
        }
    }
    return nil
}

type unbalancedErr struct {
    at int
    c  byte
}

func (e unbalancedErr) Error() string {
    return fmt.Sprintf("unbalanced %v at %v", string(e.c), e.at)
}

func balance1(input string) error {
    // a stack which have all opening tags
    stackO := stack.New()
    //create a map which have equivalent closing tags
    stackmap := map[string]string{"[": "]", "(": ")", "{": "}"}

    //looping on all string chars
    for i, num := range input {
        str := string(num)
        //Find all opening tag and push in stack until you get first closing tag
        if str == "{" || str == "[" || str == "(" {
            stackO.Push(str)
        }
        // if it is a closing tag match this with last opening tag from stack
        if str == "}" || str == "]" || str == ")" {
            ot := stackO.Peek()
            //if no opening tag found means stack is empty  , quit and report error
            if ot == nil {
                return fmt.Errorf("Not balanced %v at %v", str, i)
            }
            closing := stackmap[ot.(string)]
            // if closing tag does not match with its equivalent opening tag means not balanced , quit and report error
            if closing != str {
                return fmt.Errorf("Not balanced %v at %v", str, i)
            } else {
                // remove opening tag from stack
                stackO.Pop()
            }
        }
    }
    return nil
}

bench_test.go

package main

import "testing"

// var input = "(a[0]+b[2c[6]])){24+53}"
var input = "(a[0]+b[2c[6]]){24+53}"

func BenchmarkBalance1(b *testing.B) {
    for i := 0; i < b.N; i++ {
        balance1(input)
    }
}

var bInput = []byte(input)
var bChars = []byte("[]{}()")
var brackets = map[byte]byte{'[': ']', '(': ')', '{': '}'}

func BenchmarkBalance2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        balance2(bInput, brackets, bChars)
    }
}

结果

$ go test -bench=. -count=4 -benchmem
goos: linux
goarch: amd64
pkg: test/balanced
BenchmarkBalance1-4      1000000          1326 ns/op         240 B/op         10 allocs/op
BenchmarkBalance1-4      1000000          1379 ns/op         240 B/op         10 allocs/op
BenchmarkBalance1-4      1000000          1332 ns/op         240 B/op         10 allocs/op
BenchmarkBalance1-4      1000000          1325 ns/op         240 B/op         10 allocs/op
BenchmarkBalance2-4      5000000           370 ns/op           0 B/op          0 allocs/op
BenchmarkBalance2-4      5000000           371 ns/op           0 B/op          0 allocs/op
BenchmarkBalance2-4      5000000           373 ns/op           0 B/op          0 allocs/op
BenchmarkBalance2-4      5000000           373 ns/op           0 B/op          0 allocs/op
PASS
ok      test/balanced   14.397s