Given an expression string exp , write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in 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()
}
}
}
}
package main
import (
"fmt"
stack "github.com/golang-collections/collections/stack"
)
func main() {
s := "(a[0]+b[2c[6]])){24+53}"
// 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 _, num := range s {
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 {
fmt.Println("Not balanced", str)
break
}
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 {
fmt.Println("Not balanced", str)
break
} else {
// remove opening tag from stack
stackO.Pop()
}
}
}
}
Playground: https://play.golang.org/p/os_imr32NPt
my take
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)
}
}
results
$ 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