写一个函数，计算一个四则运算表达式的值。有加减乘除和括号，空格忽略。不许使用eval等直接求值的函数。

    1. function calc(str) {
    2.   // TODO
    3. }
    5. calc('1 + 2 + 3') // 6
    6. calc('1+2+3') // 6
    7. calc('1+2*3') // 7
    8. calc('(1+2)*3+4') // 13
    9. 例如: 需要计算 ： 3 * (1 + 2 ) * 5 那么先计算 1+2，我们记做 1 2 + 再计算 3 * (1 + 2) 记做 3 1 2 + * 最后计算 3 * (1 + 2 ) * 5 记做 3 1 2 + * 5 * 提示：利用栈（周六课程讲解）
    11. 然后再从左到右计算。
    13. 答案:
    15. function calc(str){
    16.   const list = str.match(/(\d+|[+-\\*/()])/g)
    18. }
    19. 答案：
    21. // 定义操作符优先级
    22. const precedence = {
    23.   '+' : 1,
    24.   '-' : 1,
    25.   '*' : 2,
    26.   '/' : 2,
    27.   '(' : 0,
    28.   ')' : 0
    29. }
    32. // 出栈(pop stack)直到断言函数(prediction function) 返回false
    33. // 并返回最终的结果
    34. function poptill(stack, prediction) {
    35.   let o = null
    36.   let r = []
    37.   while(o = stack.pop()) {
    38.     if(!prediction(o)) {
    39.       stack.push(o)
    40.       break
    41.     }
    42.     r.push(o)
    43.   }
    44.   return r
    45. }
    47. // 将中缀(infix)序列转成后缀(postfix)序列，
    48. // 比如 A + B -> A B +
    49. // 再比如 A + B * C -> A B C * +
    50. // 再比如 A * (B + C) -> A B C + *
    51. // 本质上 ABC的相对顺序不变，后缀序列的操作符会在不同的地方
    52. function infix2postfix(list){
    54.   // 操作符栈
    55.   const opstack = []
    57.   // 后缀序列结果
    58.   let r = []
    60.   list.forEach(c => {
    61.     if(/(\+|-|\*|\/)/.test(c)) {
    62.       const ops = poptill(opstack, op => precedence[op] >= precedence[c])
    63.       r = r.concat(ops)
    64.       opstack.push(c)
    65.     }
    66.     else if(c === '(') {
    67.       opstack.push(c)
    68.     }
    69.     else if(c === ')') {
    70.       const ops = poptill(opstack, op => op !== '(')
    71.       opstack.pop()
    72.       r = r.concat(ops)
    73.     }
    74.     else {
    75.       r.push(c)
    76.     }
    77.   })
    78.   opstack.reverse().forEach(x => r.push(x))
    79.   return r
    80. }
    82. // 利用stack对后缀序列求值
    83. function evaluate(list) {
    84.   list = list.reverse()
    85.   const stack = []
    86.   while(list.length > 0) {
    87.     const c = list.pop()
    88.     if(/(\+|-|\*|\/)/.test(c)) {
    89.       const o1 = Number(stack.pop())
    90.       const o2 = Number(stack.pop())
    91.       switch(c) {
    92.         case '+' :
    93.           stack.push(o1 + o2)
    94.           break
    95.         case '-' :
    96.           stack.push(o1 - o2)
    97.           break
    98.         case '*' :
    99.           stack.push(o1 * o2)
    100.           break
    101.         case '/' :
    102.           stack.push(o1 / o2)
    103.           break
    104.       }
    105.     }
    106.     else {
    107.       stack.push(c)
    108.     }
    109.   }
    110.   return stack[0]
    111. }
    113. function calc(str) {
    114.   const list = str.match(/(\d+|\+|-|\*|\/|[()])/g)
    115.   const postfixs = infix2postfix(list)
    116.   return evaluate(postfixs)
    117. }