type MinStack struct {
	stack []int
	minStack []int
}
func Constructor() MinStack {
	ms := new(MinStack)
	ms.stack = []int{}
	ms.minStack = []int{}
	return *ms
}
func (this *MinStack) Push(val int)  {
	this.stack = append(this.stack, val)
	if len(this.minStack) == 0 || this.minStack[len(this.minStack)-1] > val{
		this.minStack = append(this.minStack, val)
	}else{
		this.minStack = append(this.minStack, this.minStack[len(this.minStack)-1])
	}
}
func (this *MinStack) Pop()  {
	this.minStack = this.minStack[:len(this.minStack)-1]
	this.stack = this.stack[:len(this.stack)-1]
}
func (this *MinStack) Top() int {
	return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
	return this.minStack[len(this.minStack)-1]
}

func evalRPN(tokens []string) int {
	var stack []string
	for i := 0; i < len(tokens); i++{

		if tokens[i] == "+"{
			v1,_ := strconv.Atoi(stack[len(stack)-2])
			v2,_ := strconv.Atoi(stack[len(stack)-1])
			newValue := v1+v2
			stack = stack[:len(stack)-2]
			stack = append(stack, strconv.Itoa(newValue))

		}else if tokens[i] == "-"{
			v1,_ := strconv.Atoi(stack[len(stack)-2])
			v2,_ := strconv.Atoi(stack[len(stack)-1])
			newValue := v1 - v2
			stack = stack[:len(stack)-2]
			stack = append(stack, strconv.Itoa(newValue))
		}else if tokens[i] == "*"{
			v1,_ := strconv.Atoi(stack[len(stack)-2])
			v2,_ := strconv.Atoi(stack[len(stack)-1])
			newValue := v1 * v2
			stack = stack[:len(stack)-2]
			stack = append(stack, strconv.Itoa(newValue))
		}else if tokens[i] == "/"{
			v1,_ := strconv.Atoi(stack[len(stack)-2])
			v2,_ := strconv.Atoi(stack[len(stack)-1])
			newValue := v1 / v2
			stack = stack[:len(stack)-2]
			stack = append(stack, strconv.Itoa(newValue))
		}else{
			stack = append(stack, tokens[i])
		}
	}
	res,_ := strconv.Atoi(stack[0])
	return res
}

func decodeString(s string) string {
	var stack []byte
	bs := []byte(s)
	for i:=0; i<len(bs); i++{
		if bs[i] == ']'{
			combine(&stack)
		}else{
			stack = append(stack, bs[i])
		}
	}
	return string(stack)
}
// first check algo, and then check nums
func combine(stack *[]byte){
	var tmp string
	for len(*stack)>0{
		item := (*stack)[len(*stack)-1]
		*stack = (*stack)[:len(*stack)-1]
		if item!='['{
			if isAlpha(item){
				tmp+=string(item)
			}
		}else{
			break
		}
	}
	var nums string
	for len(*stack)>0{
		item := (*stack)[len(*stack)-1]
		*stack = (*stack)[:len(*stack)-1]
		if isNum(item)==true{
			nums+=string(item)
		}else{
			*stack = append(*stack, item)
			break
		}
	}
	numint, _ := strconv.Atoi(reverse(nums))
	for i:=0;i<numint;i++{
		for j:=len(tmp)-1;j>=0;j--{
			*stack = append(*stack, tmp[j])
		}
	}
}
func isAlpha(a byte)bool{
	if a>='a' && a<='z'{return true}else{return false}
}
func isNum(a byte)bool{
	if a>='0' && a<='9'{return true}else{return false}
}
func reverse(s string) string{
	bs:= []byte(s)
	for i:=0;i<len(bs)/2;i++{
		tmp := bs[i]
		bs[i] = bs[len(bs)-1-i]
		bs[len(bs)-1-i]=tmp
	}
	return string(bs)
}