9月
13

简单算式字符串计算

技术

给你一个简单的包含加减乘数括号的算式字符串，其中的数字都不小于0且做除法的时候去整即可，请算出该表达式的值

先给出一个讲的不错的链接：中缀表达式转换为后缀表达式

这里大概描述一下流程：

中缀表达式转后缀表达式

首先，需要将普通的中缀表达式转变为后缀表达式，准备一个栈 stack 和存储结果的数组 resultArr ，开始遍历字符串

如果为数字，则直接将其添加到结果resultArr中
如果遇到运算符号，则先将 stack 中优先级大于等于它的运算符号 Pop 至 resultArr 中，之后将当前运算符号加入到 stack 中
如果遇到 ( ，则直接将其添加到 stack 中
如果遇到 ) ，则将 stack 中的运算符号依次 Pop 至 resultArr 中，直到遇到一个 ( 为止，将那个 ( Pop掉，但是并不加入到 resultArr 中

当字符串遍历结束后，如果 stack 中还有运算符的话，则将其全部 Pop 至 resultArr 中。至此为止，resultArr 就为后缀表达式了。

后缀表达式计算

准备一个栈 stack ，开始遍历 resultArr

如果遇到的为数字，则将其 Push 到 stack 中
如果遇到的为运算符号，则从 stack 中 Pop 出来两个数字，用那个运算符计算，将得到的结果 Push 回 resultArr 中

最后遍历结束 resultArr 后，stack 中仅有一个数字，此为结果。

代码

var opts = map[rune]int{
  '+': -1,
  '-': -2,
  '*': -3,
  '/': -4,
  '(': -5,
  ')': -6,
}

var optFuncs = map[int]func(a, b int) int{
  opts['+']: func(a, b int) int { return a + b },
  opts['-']: func(a, b int) int { return a - b },
  opts['*']: func(a, b int) int { return a * b },
  opts['/']: func(a, b int) int { return a / b },
}

var priority = map[int]int{
  opts['+']: 1,
  opts['-']: 1,
  opts['*']: 2,
  opts['/']: 2,
}

func calculate(s string) int {
  var postFixs []int
  stack := Stack{}
  num := 0
  s += " "

  for i, b := range s {
    switch {
    case isNumber(b):
      num = num*10 + int(b-'0')
      if !isNumber(rune(s[i+1])) {
        postFixs = append(postFixs, num)
        num = 0
      }
    case isOpt(b):
      for !stack.Empty() && stack.Peek() != opts['('] &&
        priority[stack.Peek()] >= priority[opts[b]] {
        postFixs = append(postFixs, stack.Pop())
      }
      stack.Push(opts[b])
    case isBracket(b):
      if b == '(' {
        stack.Push(opts[b])
      }
      if b == ')' {
        for !stack.Empty() && stack.Peek() != opts['('] {
          postFixs = append(postFixs, stack.Pop())
        }
        if !stack.Empty() {
          stack.Pop()
        }
      }
    }
  }
  for !stack.Empty() {
    postFixs = append(postFixs, stack.Pop())
  }
  tmpStack := Stack{}
  for _, v := range postFixs {
    if v >= 0 {
      tmpStack.Push(v)
    } else {
      v2 := tmpStack.Pop()
      v1 := tmpStack.Pop()
      tmpStack.Push((optFuncs[v])(v1, v2))
    }
  }
  return tmpStack.Pop()
}

func isNumber(b rune) bool {
  return b >= '0' && b <= '9'
}

func isOpt(b rune) bool {
  return b == '+' || b == '-' || b == '*' || b == '/'
}

func isBracket(b rune) bool {
  return b == '(' || b == ')'
}

type Stack []int

func (s *Stack) Push(d int) {
  *s = append(*s, d)
}

func (s *Stack) Pop() int {
  l := len(*s)
  d := (*s)[l-1]
  *s = (*s)[:l-1]
  return d
}

func (s Stack) Peek() int {
  return s[len(s)-1]
}

func (s Stack) Empty() bool {
  return len(s) == 0
}

func main() {
  calculate("(1+(4+5/2)-3)+(6+8)")
}

Schwarzeni

中缀表达式转后缀表达式

后缀表达式计算

代码