关于一道面试题【字符串 '1 + (5 - 2) * 3',怎么算出结果为10,'eval'除外】

最近徘徊在找工作和继续留任的纠结之中,在朋友的怂恿下去参加了一次面试,最后一道题目是:

写一个函数,输入一个字符串的运算式,返回计算之后的结果。例如这样的: ‘1 + (5 - 2) * 3’,计算出结果为10

最开始看到这个题目的时候,我脑中的第一反应就是eval,真的太直接了。但是我就不明白为什么这竟然是最后一道题目,我也不知道为什么还会考eval的运用,因此当时也很犹豫要不要用eval。因为eval有一系列的问题:

  • eval会改变当前的作用域,除非函数直接调用,并且是eval本身执行
  • eval可能会造成xss攻击,除非你对其中的字符串特别放心

当时只是觉得可以使用正则匹配运算符,然后使用递归计算,就只写了个思路,回来之后就按照这个方式实现一下。这里作为自己的解决方式,测试用例设计的也不够全面,如果各位有更好的方法,可以拿出来分享。

如果我拿个’1 + (5 - 2) * 3’这个式子我是怎么想的:

  • 看成 1 + x * 3
  • 算出x,x的计算就需要匹配括号,这个倒不是很难
  • 计算出x之后,替换成 1 + 3 * 3
  • 之后按照/%*的优先级要大于+-,先匹配计算出 3 * 3
  • 替换成 1 + 9
  • 最后得出 10

讲白了就是有括号,先计算括号中的算是,然后进行结果替换之后再进行后面的运算,整体而言就是一系列的‘递归 + 匹配’

/**
 * myEval
 * @param  string str 字符串
 * @return 返回计算后的值     [description]
 */
function myEval(str) {
  // 如果包含括号,则先进括号中的计算
  // 计算规则为:先进行括号匹配拆开,单个计算之后再进行拼接
  // 例如:((1 + 2) + 3 / (4 % 6)) * 6的计算顺序是:
  // -> ((1 + 2) + 3 / (4 % 6)) * 6
  // -> (1 + 2) + 3 / (4 % 6)
  // -> 1 + 2
  // -> 3 + 3 / (4 % 6)
  // -> 4 % 6
  // -> 3 + 3 / 4
  // -> 3 / 4
  // -> (3 + 0.75) * 6
  // -> 3 + 0.75
  // -> 3.75 * 6
  // -> 22.5
  if (exists(str, '(')) {
    const bracketStr = getMatchStr(str);
    const nextResult = myEval(bracketStr);
    const replaceStr = str.replace(`(${bracketStr})`, nextResult)

    // 如果子字符串中存在'3 + 3 / (4 % 6)' 这样的式子,说明第一个括号中的内容计算完成了
    // 这样就可以接着递归进行第二个括号中的算式计算
    if (exists(replaceStr, '(')) {
      return myEval(replaceStr);
    } else {
      // 如果是类似于'1 + 2 / 3'的式子,则直接进行计算返回结果
      return innerBracketCacl(replaceStr);
    }
  } else {
    return innerBracketCacl(str);
  }
}

取一个叫做myEval的函数,主要进行流程的控制,如果遇到的是括号中的内容,则先进行括号中的运算,否则,直接进行常规表达式计算。

/**
 * 获取匹配的字符串
 * @param  string str 
 * @return string 返回的匹配结果
 */
function getMatchStr(str) {
  // 匹配类似于这样的式子: 
  // '((1 + 2) / 3) * 4'        ->  ((1 + 2) / 3)
  // '1 * (2 + 3) / (5 - 6)'    ->  2 + 3
  const regexp = /\([^\)]+\)[^\(]+\)|\((.*?)\)/;
  const regexp2 = /\((.*)\)/;
  let matches = str.match(regexp);
  let bracketStr = matches[1] || matches[0];

  if (exists(bracketStr, '(') && !exists(bracketStr, ')')) {
    // 类似于这样的式子'((1 + 2) / (3 - 7)) * 4'
    // 那么匹配出来的就是'(1 + 2'
    // 显然不是我想要的结果,我只需要解掉第一层的括号就可以按照之前的方式计算了
    // 用第二个正则匹配的就是'(1 + 2) / (3 - 7)'
    // 我只需要按照之前的方式先计算这个式子就好
    bracketStr = str.match(regexp2)[1];
  } else if(bracketStr.indexOf('(') === 0) {
    bracketStr = bracketStr.slice(1, -1);
  }

  return bracketStr;
}

获取匹配字符子串,主要是进行规则匹配,分布计算。

/**
 * 计算表达式
 * 例如有这样的式子: '1 + 2 / 3'
 * 那么会先计算'2 / 3'
 * @param  string str
 * @return string     结果
 */
function innerBracketCacl(str) {
  const matches = str.match(/[\/\*%]/g);
  let firstPriorityResult = str;

  if (matches) {
    firstPriorityResult = stepFirstPriority(str);
  }

  return stepSecondPriority(firstPriorityResult);
}

简单的运算式计算,即不包含括号的计算,先计算*/%的运算符,然后计算+-

/**
 * 第一优先级的运算
 * 这里的第一优先级为'%/*'
 * @param  string str 
 * @return number 返回计算结果 
 */
function stepFirstPriority(str) {
  const matches = str.match(/[\/\*%]/g);
  if (!matches) {
    return str;
  } else {
    const newStr = caclPart('/%*', str);
    return stepFirstPriority(newStr);
  }
}

/**
 * 第二优先级的运算
 * 这里的第一优先级为'+-'
 * @param  string str 
 * @return number 返回计算结果 
 */
function stepSecondPriority(str) {
  if (!isNaN(Number(str))) {
    return str;
  } else {
    const newStr = caclPart('+-', str);
    return stepSecondPriority(newStr);
  }
}

这上面是运算优先级的计算方式,先乘除后加减,计算之后进行字符串替换,然后递归计算。

/**
 * 计算类似于 '1 + 2', '3 / 4'的子算式
 * @param  string shouldOprs 包含的运算符,例如('/%*', '+-')
 * @param  string str        计算的子字符串,例如( 1 + 2 / 4 )
 * @return string            返回计算后的子字符串,例如( 1 + 0.5 )
 */
function caclPart(shouldOprs, str) {
  let newStr = '';
  for (let i = 0; i < str.length; i++) {
    let s = str[i];
    if (exists(shouldOprs, s)) {
      // 截取字符串的左侧
      // 例如字符串为'3 + 3 / 4', 那么左侧就是'3 + 3 /',右侧则是 / 4
      // 目的是为了接下来的匹配左右两侧的数字
      let leftStr = str.slice(0, i + 1);
      let rightStr = str.slice(i);
      // 左侧的正则为/((\d\.)*\d+)\s*\+$/,其中最后一个'+'是动态匹配的字符串
      // 右侧的正则为/\+\s*((\d\.)*\d+)/,其中最后一个'+'是动态匹配的字符串
      const leftNum = new RegExp('\((\\d\\.)*\\d+\)\\s\*\\' + s + '$', 'g').exec(leftStr)[1];
      const rightNum = new RegExp('\\' + s + '\\s\*\((\\d\\.)*\\d+\)').exec(rightStr)[1];
      // 计算出值后进行字符串替换
      // 比如'3 + 3 / 4' -> '3 + 0.75'
      // 单个计算完成之后跳出循环,之后继续进行后面的操作
      const result = cacl(leftNum, rightNum, s);
      newStr = str.replace(new RegExp('(\\d\\.)*\\d+\\s\*\\' + s + '\\s\*(\\d\\.)*\\d+'), result);
      break;
    }
  }
  return newStr;
}

至此,这就是我的全部思路以及实现方式。

其中有一些正则表达式写不出,想来正则学得还是不够,只能用一些取巧的办法。测试用例也设计得不是太全面,可能会存在一些问题,但是就目前的测试来说,简单的算是是能通过的。

性能问题上:因为频繁的调用递归,致使复杂度大大增大,时间运行得也比原生eval时间要长。以下是我的测试例子:

const str = '1 + 2';
const str2 = '1 + 2 - 3';
const str3 = '1 + 2 + 3 / 4';
const str4 = '1 + 2 + 3 / 4 % 5';
const str5 = '1 + 2 * (3 + 4) + 5';
const str6 = '(1 + 2) * (3 + 4) + 5';
const str7 = '((1 + 2) + 3 / (4 % 6)) * 6';

console.time('myEval');
console.log('myEval: ',  myEval(str));
console.log('myEval: ',  myEval(str2));
console.log('myEval: ',  myEval(str3));
console.log('myEval: ',  myEval(str4));
console.log('myEval: ',  myEval(str5));
console.log('myEval: ',  myEval(str6));
console.log('myEval: ',  myEval(str7));
console.timeEnd('myEval')

console.time('eval');
console.log('eval: ',  eval(str));
console.log('eval: ',  eval(str2));
console.log('eval: ',  eval(str3));
console.log('eval: ',  eval(str4));
console.log('eval: ',  eval(str5));
console.log('eval: ',  eval(str6));
console.log('eval: ',  eval(str7));
console.timeEnd('eval')

关于js实现eval的方式:

//计算表达式的值
function evil(fn) {
    var Fn = Function;  //一个变量指向Function,防止有些前端编译工具报错
    return new Fn('return ' + fn)();
}

// jquery2.0.3实现方式:
// Evaluates a script in a global context
globalEval: function( code ) {
    var script,
            indirect = eval;
 
    code = jQuery.trim( code );
 
    if ( code ) {
        // If the code includes a valid, prologue position
        // strict mode pragma, execute code by injecting a
        // script tag into the document.
        if ( code.indexOf("use strict") === 1 ) {
            script = document.createElement("script");
            script.text = code;
            document.head.appendChild( script ).parentNode.removeChild( script );
        } else {
        // Otherwise, avoid the DOM node creation, insertion
        // and removal by using an indirect global eval
            indirect( code );
        }
    }
}

参考资料:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏青青天空树

小白详细讲解快速幂--杭电oj2035-A^B

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

1453
来自专栏菜鸟前端工程师

JavaScript学习笔记005-运算符

912
来自专栏mathor

C++STL中vector使用策略(二)

1804
来自专栏二进制文集

LeetCode 004 Median of Two Sorted Arrays 详细分析

题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/

1111
来自专栏数据结构与算法

P1168 中位数

题目描述 给出一个长度为N的非负整数序列A[i],对于所有 ]的中位数。 个数的中位数。 输入输出格式 输入格式: 输入文件median.in的第1...

31911
来自专栏tkokof 的技术,小趣及杂念

sizeof 知多少?

稍熟悉C/C++的朋友,对于sizeof肯定不陌生,通过他我们可以知晓某个类型或者实例的内存大小(以字节计),但是如果深入一下sizeof计算的细节,想来大部分...

720
来自专栏大数据风控

Python中字段抽取、字段拆分、记录抽取

1、字段抽取 字段抽取是根据已知列数据的开始和结束位置,抽取出新的列 字段截取函数:slice(start,stop) 注意:和数据结构的访问方式一样,开始位置...

2928
来自专栏架构之路

一条直线上N个线段所覆盖的总长度

转自http://blog.csdn.net/bxyill/article/details/8962832 问题描述: 现有一直线,从原点到无穷大。 这条直线上...

3655
来自专栏WD学习记录

LeetCode Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

1021
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

2612

扫码关注云+社区

领取腾讯云代金券