面试题解法二:逆波兰表达式计算'1 + (5 - 2) * 3'

昨天发了一个面试题:关于一道面试题【字符串 ‘1 + (5 - 2) * 3’,怎么算出结果为10,’eval’除外】,受到了各位大大的指点,用一个比较简单的解法就能够计算出来,因此自己在下班后按照各位的指点又实现了一遍,这里贴出来供大家参考。

了解前缀、中缀、后缀表达式

关于概念这里简单贴一下,想了解更多的可以自行Google

  • 前缀表达式:是一种没有括号的算术表达式,与中缀表达式不同的是,其将运算符写在前面,操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz,前缀表达式也称为“波兰式”。例如,- 1 + 2 3,它等价于1-(2+3)。
  • 中缀表达式:是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的算术表示方法。
  • 后缀表达式:指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行,后缀表达式也称为“逆波兰式”。例如:1 2 3 4 + * + 5 +

注: 与前缀表达式(例:+ 3 4)或后缀表达式(例:3 4 +)相比,中缀表达式不容易被计算机解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。

中缀表达式如何转换为后缀表达式以及运算

一、 将中缀表达式转换成后缀表达式算法:

  1. 从左至右扫描一中缀表达式。
  2. 若读取的是操作数,则判断该操作数的类型,并将该操作数存入操作数堆栈
  3. 若读取的是运算符
    • 该运算符为左括号”(“,则直接存入运算符堆栈。
    • 该运算符为右括号”)”,则输出运算符堆栈中的运算符到操作数堆栈,直到遇到左括号为止。
    • 该运算符为非括号运算符:
      • 若运算符堆栈栈顶的运算符为括号,则直接存入运算符堆栈。
      • 若比运算符堆栈栈顶的运算符优先级高或相等,则直接存入运算符堆栈。
      • 若比运算符堆栈栈顶的运算符优先级低或者优先级相等,则输出栈顶运算符到操作数堆栈,直到比运算符堆栈栈顶的运算符优先级低或者为空时才将当前运算符压入运算符堆栈。
  4. 当表达式读取完成后运算符堆栈中尚有运算符时,则依序取出运算符到操作数堆栈,直到运算符堆栈为空。

二、逆波兰表达式求值算法:

  1. 循环扫描语法单元的项目。
  2. 如果扫描的项目是操作数,则将其压入操作数堆栈,并扫描下一个项目。
  3. 如果扫描的项目是一个二元运算符,则对栈的顶上两个操作数执行该运算。
  4. 如果扫描的项目是一个一元运算符,则对栈的最顶上操作数执行该运算。
  5. 将运算结果重新压入堆栈。
  6. 重复步骤2-5,堆栈中即为结果值。

看上面的概念我都看晕了,接下来以一个例子讲解:

1 + 2 * (3 + 4) + 5
originArr      代表字符串转化为数组之后的数组
operatorArr    代表运算符数组
reverseArr     代表后缀表达式数组
下面是一步一步的过程

originArr:   ["1","+","2","*","(","3","+","4",")","+","5"]

operatorArr: []
reverseArr:  ["1"]
 
operatorArr: ["+"]
reverseArr:  ["1"]

operatorArr: ["+"]
reverseArr:  ["1","2"]

operatorArr: ["+","*"]
reverseArr:  ["1","2"]

operatorArr: ["+","*","("]
reverseArr:  ["1","2"]

operatorArr: ["+","*","("]
reverseArr:  ["1","2","3"]

operatorArr: ["+","*","(","+"]
reverseArr:  ["1","2","3"]

operatorArr: ["+","*","(","+"]
reverseArr:  ["1","2","3","4"]

operatorArr: ["+","*"]
reverseArr:  ["1","2","3","4","+"]

operatorArr: ["+"]
reverseArr:  ["1","2","3","4","+","*","+"]

operatorArr: ["+"]
reverseArr:  ["1","2","3","4","+","*","+","5"]

operatorArr: []
reverseArr:  ["1","2","3","4","+","*","+","5","+"]

更多的可以参看小茗同学的这篇文章 或者 逆波兰表达式

实现过程

这里直接贴代码,在代码中有详细的解析

const ADD = '+';				// 加常量
const SUB = '-';				// 减常量
const MUL = '*';				// 乘常量
const DIV = '/';				// 除常量
const MOD = '%';				// 取余常量
const priorityMap = {
	'+': 1, 
	'-': 1,
	'*': 2,
	'/': 2,
	'%': 2
};

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';

/**
 * 获取逆波兰数组
 * @param  string str 运算字符串
 * @return Array     逆波兰数组
 */
function reversePolish(str) {
	str = str.replace(/\s*/g, '');
	const originArr = str.split('');
	// 保存最终逆波兰数组的数组
	let reverseArr = [];
	// 保存运算符的数组
	let operatorArr = [];

	originArr.forEach(origin => {
		// 如果是数字,则直接push最终逆波兰的数组
		if (!isNaN(Number(origin))) {
			reverseArr.push(origin);
		} else {
			// 如果运算符数组为空,说明还没有遇到运算符
			// 直接push进栈
			if (operatorArr.length === 0) {
				operatorArr.push(origin);
			} else {
				// 进行比较,决定是入栈还是出栈
				// 1. '*/%'这三类因为具有最高优先级,所以直接push
				// 2. '('因为不和谁进行比较,也可以直接push
				const originPriority = priorityMap[origin];
				if (originPriority === 2 || origin === '(') {
					operatorArr.push(origin);
				} else {
					// 获取运算符中是否存在了'(',为后面的判断作准备
					const lastBracketIndex = operatorArr.lastIndexOf('(');
					// 如果循环到了')',说明运算数组中必定存在一个'('
					// 则直接截取从最后到'('的数组,直接push进返回结果的数组中
					if (origin === ')') {
						const includeLeftBracketArr = operatorArr.splice(lastBracketIndex).slice(1).reverse();
						reverseArr = reverseArr.concat(includeLeftBracketArr);
					} else {
						// 否则,我只需要比较运算数组中最后一个运算符就好
						// 如果循环出的运算符的优先级大于或者等于最后一个运算符的优先级,那么直接push
						const topOperator = operatorArr[operatorArr.length - 1];
						if (originPriority >= priorityMap[topOperator]) {
							operatorArr.push(origin);
						} else {
							// 否则,就需要判断运算符数组中是否已经存在了'('
							// 如果存在'(', 则我只需要截取到'('的数组就可以了
							// 如果不存在,我只需要将整个运算符数组进行拼接就好,因为循环出来的运算符的优先级肯定是小于或者等于运算符数组中的优先级的
							if (lastBracketIndex !== -1) {
								const includeLeftBracketArr = operatorArr.splice(lastBracketIndex + 1).reverse();
								reverseArr = reverseArr.concat(includeLeftBracketArr);
							} else {
								reverseArr = reverseArr.concat(operatorArr.reverse());
								operatorArr = [];
							}
							// 最后,把这个运算符push进栈
							operatorArr.push(origin);
						}
					}
				}
			}
		}
	});

	// 最后,如果运算符中还有运算符,进行拼接就好了
	if (operatorArr.length > 0) {
		reverseArr = reverseArr.concat(operatorArr.reverse());
		operatorArr = [];
	}

	return reverseArr;
}

/**
 * 真正的计算过程
 * @param  string left  左边的数字字符串
 * @param  string right 右边的数字字符串
 * @param  string opr   运算符
 * @return number       结果
 */
function cacl(left, right, opr) {
	left = Number(left);
	right = Number(right);
	switch(opr) {
		case MUL:
			return left * right;
		case DIV:
			return left / right;
		case MOD: 
			return left % right;
		case ADD:
			return left + right;
		case SUB:
			return left - right;
		default: 
			return 0;
	}
}


/**
 * 计算逆波兰数组中的值
 * @param  string str 运算字符串
 * @return number     结果
 */
function myEval(str) {
	const reversePolishArr = reversePolish(str);
	const tempArr = [];
	reversePolishArr.forEach(origin => {
		// 数字直接push
		if (!isNaN(Number(origin))) {
			tempArr.push(origin);
		} else {
			// 如果遇到运算符,则pop出前两个数
			// 根据运算符得出结果后再push
			const num1 = tempArr.pop();
			const num2 = tempArr.pop();
			const result = cacl(num2, num1, origin);
			tempArr.push(result);
		}
	});
	return tempArr[0];
}

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')

运行时间:

因为换了台电脑,所以原生eval对比上一篇文章中有比较大的影响,但是就时间的对比来说还是有接近3倍左右的差距。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Ryan Miao

java中遇到过的String的一些特性

1.string对象是final的? 1 String str="asdfdf"; 2 str.replace("as",""); 3 System.out.p...

36090
来自专栏landv

Java基本语法

16710
来自专栏曾大稳的博客

c语法进阶

不管是基本数据类型还是结构体,c都是值传递,和java不同的是,java基本数据类型是值传递,对象是引用传递。所以在c当中一般都是指针传递

17420
来自专栏极乐技术社区

使用ES6新特性开发微信小程序(2)

Template Literals(模板对象) ES6中的模板字符串(Template String)是一种能在字符串文本中内嵌表达式的字符串字面量(Strin...

33060
来自专栏码云1024

JAVA 第二天 关键字

29870
来自专栏Vamei实验室

Python补充03 Python内置函数清单

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。 Python内置(built-in)函数随着py...

19760
来自专栏土豆专栏

Java面试之数据类型(一)

封装类是引用类型,基本类型在传递参数的时候都是按值传递,而封装类型是按引用传递的(其实引用也是按值传递的,但是传递的是对象的地址)

19420
来自专栏函数式编程语言及工具

Scalaz(5)- typeclass:my typeclass scalaz style-demo

  我们在上一篇讨论中介绍了一些基本的由scalaz提供的typeclass。这些基本typeclass主要的作用是通过操作符来保证类型安全,也就是在前期编译时...

21090
来自专栏Python小屋

常用正则表达式锦集与Python中正则表达式的用法

1、常用正则表达式 最简单的正则表达式是普通字符串,只能匹配自身 '[pjc]ython'可以匹配'python'、'jython'、'cython' '[a-...

32650
来自专栏个人随笔

C#基础 1(异同与区别及其特点)

一.值类型与引用类型的主要区别   1.值类型分配在栈上,引用类型分配在堆上   2.值类型继承自ValueType,引用类型不会继承自ValueType   ...

29050

扫码关注云+社区

领取腾讯云代金券