#55 奇怪的表达式


  • 0
    administrators

    @Sunjourney 我还是把题目改成整数就好了。哈哈。


  • 0

    本来还想搞成三趟编译器加虚拟机的形式的,结果发现常量折叠完这题就解完了。。。。

    class Stream {
      constructor(tokens) {
        this.tokens = tokens
        this.pos = 0
      }
      
      get next() {
        return this.tokens[this.pos++] || ''
      }
      
      cancel() {
        this.pos--
      }
      
      get done() {
        return this.pos >= this.tokens.length
      }
      
      get rest() {
        return this.tokens.slice(this.pos)
      }
      
      transaction(fn) {
        const rpos = this.pos
        const ret = fn()
        if (ret === failure) {
          this.pos = rpos
          return failure
        }
        return ret
      }
    }
    
    function preventRec(fn) {
      const stack = []
      return stream => {
        if (stack.includes(stream.pos)) {
          return ignore
        }
        stack.push(stream.pos)
        const ret = fn(stream)
        stack.pop()
        return ret
      }
    }
    
    const failure = Symbol('failure')
    const ignore = Symbol('ignore')
    
    const eq = str => stream => stream.transaction(() => stream.next == str ? ignore : failure)
    
    const re = regex => fn => stream => stream.transaction(() => {
      const ret = stream.next.match(regex)
      if (!ret) return failure
      return fn(ret)
    })
    
    const chain = (...parsers) => fn => stream => stream.transaction(() => {
      const arr = []
      for (const parser of parsers) {
        const result = parser(stream)
        if (result == failure)
          return failure
        if (result != ignore)
          arr.push(result)
      }
      return fn(...arr)
    })
    
    const choice = (...parsers) => stream => {
      for (const parser of parsers) {
        const result = parser(stream)
        if (result != failure)
          return result
      }
      return failure
    }
    
    let Parser
    Parser = (() => {
      const number = re(/^((\+|\-)?Infinity|\d+(\.\d+)?)$/)(x => ({op: 'imm', value: parseFloat(x[0])}))
      let expression
      expression = choice(
        chain(
          eq(`(`),
          re(/^[\+\-\*\/\%]$/)(x => x[0]),
          s => expression(s),
          s => expression(s),
          eq(`)`)
        )((op, a, b) => ({op, a, b})),
        number
      )
      return expression
    })()
    
    const tokenizer = str => str.match(/(\+|\-)?Infinity|\d+(\.\d+)?|[\(\)\+\-\*\/]/g)
    
    const runExpression = (exp) => {
      const tokens = tokenizer(exp)
      if (!tokens) return null
      const stream = new Stream(tokenizer(exp))
      console.log(tokenizer(exp))
      const ast = Parser(stream)
      console.log(ast)
      if (stream.rest.length || ast.op == 'imm') return null
      const opmap = {
        'imm': node => exec => node.value,
        '+': node => exec => exec(node.a) + exec(node.b),
        '-': node => exec => exec(node.a) - exec(node.b),
        '*': node => exec => exec(node.a) * exec(node.b),
        '/': node => exec => exec(node.a) / exec(node.b),
        '%': node => exec => exec(node.a) % exec(node.b),
      }
      let walk
      walk = node => opmap[node.op](node)(walk)
      return walk(ast)
    }
    

  • 0
    administrators

    @CodeHz 厉害了 👍


  • 0
    管理员

    @CodeHz 666666


  • 1

    // + - * / 
    const runExpression = (exp) => {
        console.log(exp)
        let str = exp.replace(/\([^\)\()]+\)/g, (str) => {
            let res = str.match(/([\+\-\*\/])\s*(\-*\d+\.*\d*|\-*Infinity)\s*(\-*\d+\.*\d*|\-*Infinity)/)
            if (!res) return str
            return ' ' + eval(`(${res[2]})${res[1]}(${res[3]})`) + ' '
        })
        if (exp == str) return null
        let val = Number(str)
        if (val == val) return val
        return runExpression(str)
    } /* TODO */
    
    

    分享个low一点的,居然通过了……
    大神太多了,萌新瑟瑟发抖


  • 0

    @ScriptOJ 暴力破解了当前这个例子,结果发现还有其他漏洞。。。


  • 0

    @Reson_a
    '' + -0 + '' // '0'
    所以你这个结果有时候会在 应该为-Infinity的时候变成了 Infinity

    ' ' + eval((${res[2]})${res[1]}(${res[3]})) + ' ' 这里,看怎么将 -0 变成 字符串的 '-0'


  • 0

    const runExpression = str => {
      if (!str || str.trim()[0] !== '(') {
        return null
      }
    
      const stack = []
    
      const l = str.length
      let i = 0
      let c
    
      const ops = {
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        '/': (a, b) => a / b
      }
    
      let k = ''
    
      while (i < l) {
        c = str[i]
    
        switch (true) {
          case /\s+/.test(c):
            k && stack.push(+k)
            k = ''
            break
    
          case /\(/.test(c):
            stack.push('(')
            break
    
          case c === ')':
            k && stack.push(+k)
            k = ''
    
            if (stack.length < 4) {
              return null
            }
    
            const [b, a, op, s] = [
              stack.pop(),
              stack.pop(),
              stack.pop(),
              stack.pop()
            ]
    
            if (!s || s !== '(' || !op) {
              return null
            }
    
            stack.push(ops[op](a, b))
            break
    
          case !!ops[c]:
            stack.push(c)
            break
    
          case /[0-9]/.test(c):
            k += c
            break
    
          default:
            return null
        }
    
        i += 1
      }
    
      k && stack.push(+k)
      k = ''
    
      return stack.length === 1 ? stack[0] : null
    }
    

  • 0

    const runExpression = (exp) => {
      function *getTokens (str) {
        str = str.trim();
        let count = 0, i = 0;
        while(i < str.length) {
          if(str[i] === '(') ++count;
          else if(str[i] === ')') --count;
          if(count === 0 && (str[i] === ' ' || str[i] === ')')) {
            yield str.slice(0, i + 1);
            str = str.slice(i + 1).trim();
            i = 0;
            continue;
          }
          ++i;
        }
        if(str.length) yield str;
      }
      const reg = /^\(([\+\-\*\/])(.*)\)$/;
      const digital = /^\d+$/;
      const gao = (exp) => {
        exp = exp.trim();
        const match = reg.exec(exp);
        if(match == null) {
          if(digital.test(exp)) {
            return Number(exp);
          } else {
            throw new Error('not exp');
          }
        } else {
          const [$0, $1, $2] = match;
          const subs = [...getTokens($2)];
          if(subs.length !== 2) throw new Error('not exp');
          const vals = subs.map(sub => gao(sub));
          return eval(`${vals[0]} ${$1} ${vals[1]}`);
        }
      }
      try {
        if(!reg.test(exp)) throw new Error('not exp');
        return gao(exp);
      } catch (e) {
        return null;
      }
    }
    

  • 0

    分享一个用两个stack解法,一个只存括号,另一个存数字和操作符
    const runExpression = (exp) => {
      let op = [];
      let bk = [];
    
      let i = 0;
      while (i < exp.length) {
        if (exp[i] === ' ') {
          //skip, do nothing
        } else if (exp[i] === "(") {
          bk.push(exp[i]);
        } else if (exp[i] === ")") {
          if (bk.length === 0) {
            return null;
          }
          bk.pop();
        } else if (exp[i] === "+" ||
               exp[i] === "-" ||
               exp[i] === "*" ||
               exp[i] === "/") {
          op.push(exp[i]);
          
        } else if (!isNaN(exp[i])) {
          let tmp = "";
          let j = i + 1;
          while (exp[j] !== ' ' && !isNaN(exp[j])) {
            j++;
          }
          tmp = exp.slice(i, j);
          let n = parseInt(tmp);
          i = j - 1;
    
          if (op.length <= 0) {
            return null; //排除数字开头
          }
          while (op.length >= 2 && !isNaN(op[op.length - 1])) {
            let lnum = op.pop();
            let oprt = op.pop();
            if (oprt === "+") {
              n = lnum + n;
            } else if (oprt === "-") {
              n = lnum - n;
            } else if (oprt === "*") {
              n = lnum * n;
            } else if (oprt === "/") {
              n = lnum / n; 
            } else {
              return null; //排除非运算符情况
            }
          }
          op.push(n);
        } else {
          return null; 
        }
    
        i++;
      }
    
      if (bk.length !== 0 || op.length !== 1) {
        return null;
      }
    
      return op[0];
    }
    

  • 0

    输入 (+ 4 (/ 17 (* (* (+ 2 15) (* (/ 15 (+ 9 16)) (- (+ (/ (* (- (* (+ (- (+ 16 8) 17) 19) 19) 2) 3) 18) 12) 8))) (* (* (- 9 0) (+ 17 1)) (* 10 16))))),应该输出 4.000000747679204,而你输出的是 null

    说好的只操作正整数呢……怎么有0在里面


  • 0

    0_1548944337968_#55 奇怪的表达式.png


登录后回复
 

与 ScriptOJ 的连接断开,我们正在尝试重连,请耐心等待