Stack 简介
Stack 是一种抽象数据类型, 栈的操作为后进先出 (LIFO, Last In First Out), 队列为先进先出 (FIFO, First In First Out)主要操作为 push(入栈) 和 pop(出栈)
JavaScript 实现
- // https://github.com/ningh121/ds/blob/master/src/Stack.js
- class Stack {
- constructor() {
- // 使用 Array 保存栈数据
- this.stack = [];
- }
- // 压栈
- push(value) {
- this.stack.push(value);
- }
- // 出栈, 栈为空时返回 undefined
- pop() {
- return this.stack.pop();
- }
- size() {
- return this.stack.length;
- }
- empty() {
- return this.size() === 0;
- }
- }
Stack 应用
栈几乎无处不在比如日常使用的计算器大多是使用栈来完成计算任务的
最简单的计算器
最简单的计算器不考虑优先级的问题, 输入操作符时将当前值和操作符压入栈, 输入操作数时进行求值操作
JavaScript 实现
- // 简单的计算器只能做加减乘除运算, 并且没有优先级概念
- const simpleOperators = ['+', '-', '*', '/'];
- class SimpleCaculator {
- constructor() {
- this.stack = new Stack();
- this.result = 0;
- }
- enter(value) {
- if (simpleOperators.includes(value)) {
- // 读取到操作符, 将当前结果和操作符压入栈中
- // 注意! 这里没有处理多个操作符的情况
- // 当栈不为空时应该报错, 或者将栈顶操作符弹出, 压入新操作符
- this.stack.push(this.result);
- this.stack.push(value);
- } else {
- // 读取到操作数时, 如果栈为空不需要进行求值
- if (this.stack.empty()) {
- this.result = value;
- } else {
- const operator = this.stack.pop(),
- prevResult = this.stack.pop();
- switch (operator) {
- case '+':
- this.result = prevResult + value;
- break;
- case '-':
- this.result = prevResult - value;
- break;
- case '*':
- this.result = prevResult * value;
- break;
- case '/':
- this.result = prevResult / value;
- break;
- }
- }
- }
- return this.result;
- }
- }
- let simpleCaculator = new SimpleCaculator();
- console.log(simpleCaculator.enter(1)); // => 1
- console.log(simpleCaculator.enter('+')); // => 1
- console.log(simpleCaculator.enter(1)); // => 2
后缀 (逆波兰) 表示法
简单的计算器不需要考虑运算优先级的问题, 只需要能够储存两个值的栈就可以了但实现科学计算器程序则需要考虑运算优先级, 括号改变优先级等问题通常需要将中缀表示法转为逆波兰表示法, 逆波兰表示法在求值时不需要使用括号, 也不需要考虑优先级
比如: 1 + 1 * 2 转换为 1 1 2 * +,(1 + 1) * 2 转换为 1 1 + 2 *
逆波兰表达式转化步骤
读取中缀表达式, 遇到操作数直接输出;
遇到操作符时, 依次从栈中弹出优先集更高的操作符, 同时输出除括号外的操作符;
读取完毕依次输出栈中所有元素(除括号外)
( 只在处理 ) 时才输出
优先级
JavaScript 实现
- const convertToReversePolish = (infixExpression) = >{
- const operators = ['+', '-', '*', '/', '(', ')'];
- let stack = new Stack();
- let ret = [];
- // 切割表达式, 模拟读取
- infixExpression.replace(/([\d+|\+|\-|\*|\/|\(|\)])/g, (_, expression) = >{
- if (operators.includes(expression)) {
- // 读取到操作符, 输出所有优先级更低的操作符
- while (true) {
- // 栈为空, 直接将当前操作符压入栈中, 并跳出循环
- if (stack.empty()) {
- stack.push(expression);
- break;
- }
- // `(` 的优先级最高, 直接压入栈中, 并跳出循环
- if (expression === '(') {
- stack.push(expression);
- break;
- }
- const op = stack.pop();
- // `)` 的优先级最高, 只要操作符不为 `(` 则一直输出
- if (expression === ')') {
- if (op !== '(') {
- ret.push(op);
- continue;
- }
- // 跳出循环, 不需要输出 `(`
- break;
- }
- // `(` 只在处理 `)` 时出栈
- if (op === '(') {
- stack.push(op);
- stack.push(expression);
- break;
- }
- if (expression === '+' || expression === '-') {
- // `+` 和 `-` 的优先级最低
- // 除非栈顶操作符也为 `+` 和 `-`, 否则输出栈顶操作符, 并继续
- if (op !== '+' || op !== '-') {
- ret.push(op);
- continue;
- }
- }
- // 比栈顶预算符优先级相同或更低, 将操作符压回栈中, 中止
- stack.push(op);
- stack.push(expression);
- break;
- }
- } else {
- // 操作数直接输出
- ret.push(expression);
- }
- });
- // 依次弹出栈中剩下的操作符, 并输出
- while (!stack.empty()) {
- let op = stack.pop();
- if (op !== '(') {
- ret.push(op);
- }
- }
- return ret.join(' ');
- };
- console.log(convertToReversePolish('1 + 1 * 2')); // => 1 1 2 * +
- console.log(convertToReversePolish('(1 + 1) * 2')); // => 1 1 + 2 *
- console.log(convertToReversePolish('1 + 2 * 3 + (4 * 5 + 6) * 7'));
- // => 1 2 3 * + 4 5 * 6 + 7 * +
逆波兰表达式求值
逆波兰表达式求值非常简单读取到操作数时, 直接压入栈中读取到操作符时从栈中弹出两个数, 运算后将结果押回栈中
JavaScript 实现
- const evalReversePolish = (suffixExpression) => {
- const operators = ['+', '-', '*', '/'];
- let stack = new Stack();
- // 切割表达式, 模拟读取
- suffixExpression.replace(/([\d+|\+|\-|\*|\/])/g, (_, expression) => {
- if (operators.includes(expression)) {
- const val1 = stack.pop(),
- val2 = stack.pop();
- switch (expression) {
- case '+':
- stack.push(val1 + val2);
- break;
- case '-':
- stack.push(val2 - val1);
- break;
- case '*':
- stack.push(val1 * val2);
- break;
- case '/':
- stack.push(val2 / val1);
- break
- }
- } else {
- // 操作值直接压入栈中
- stack.push(parseInt(expression));
- }
- });
- return stack.pop();
- };
- console.log(
- evalReversePolish(
- convertToReversePolish('1 + 1 * 2'))); // => 3
- console.log(
- evalReversePolish(
- convertToReversePolish('(1 + 1) * 2'))); // => 4
- console.log(
- evalReversePolish(
- convertToReversePolish('1 + 2 * 3 + (4 * 5 + 6) * 7'))); // => 189
代码 https://jsbin.com/vemino/edit?js,console
来源: https://juejin.im/entry/5ac0b17e6fb9a028d700bd57