20. 有效的括号

• 用数组模拟出一个栈即可

func isValid(s string) bool {
    piars := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack := make([]byte, 10010)
    index := -1
    sb := []byte(s)
    for _, char := range sb {
        if val, ok := piars[char]; ok {
            if index < 0 {
                return false
            }
            // 需要匹配
            topVal := stack[index]
            if topVal != val {
                return false
            } else {
                index--
            }
        } else {
            index++
            stack[index] = char
        }
    }
    return index == -1
}

1047. 删除字符串中的所有相邻重复项

func removeDuplicates(s string) string {
    stack := make([]byte, 200010)
    index := -1
    for i := 0; i < len(s); i++ {
        char := s[i]
        if index == -1 {
            // push
            index++
            stack[index] = char
            continue
        }
        topVal := stack[index]
        if topVal == char {
            // pop
            index--
        } else {
            // push
            index++
            stack[index] = char
        }
    }
    res := make([]byte, index+1)
    for i := 0; i <= index; i++ {
        res[i] = stack[i]
    }
    return string(res)
}

150. 逆波兰表达式求值

• 注意这里给的已经是后缀表达式了，不用考虑中缀转后缀问题

var nums []string
var numsIndex int

var ops []string
var opsIndex int

func pushNum(x string) {
    numsIndex++
    nums[numsIndex] = x
}
func popNum() string {
    // check
    x := nums[numsIndex]
    numsIndex--
    return x
}
func pushOp(c string) {
    opsIndex++
    ops[opsIndex] = c
}
func popOp() string {
    x := ops[opsIndex]
    opsIndex--
    return x
}
func topOp() string {
    return ops[opsIndex]
}
func parse(a, b, op string) string {
    x1, _ := strconv.Atoi(b)
    x2, _ := strconv.Atoi(a)
    switch op {
    case "+":
        return strconv.Itoa(x1 + x2)
    case "-":
        return strconv.Itoa(x1 - x2)
    case "*":
        return strconv.Itoa(x1 * x2)
    case "/":
        return strconv.Itoa(x1 / x2)

    }
    return ""
}
func evalRPN(tokens []string) int {
    // init
    nums = make([]string, 10010)
    numsIndex = -1
    ops = make([]string, 10010)
    opsIndex = -1
    // pior: + - * /
    operations := map[string]int{
        "+": 1, "-": 2, "*": 3, "/": 4, "#": 5,
    }
    //pushOp("#")
    for _, token := range tokens {
        if _, ok := operations[token]; ok {
            res := parse(popNum(), popNum(), token)
            pushNum(res)
            //pushOp(token)
        } else {
            pushNum(token)
        }
    }
    res, _ := strconv.Atoi(popNum())
    return res
}

---

• 分类： 算法
• 标签： 算法基础 栈 表达式求值