栈与队列经典题目回顾：​ 有效括号/逆波兰表达

栈与队列理论基础

关于数据结构的部分，补充如下：

《再谈js数据类型与对象数据结构底层实现原理-object array map set》

《再谈Java数据结构—分析底层实现与应用注意事项》

《算法与数据结构面试通关经验总结：leetCode刷题经验》

关于leetcode，这个几个经典题目还是要记一下

栈

有效的括号

https://leetcode.cn/problems/valid-parentheses/description/

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

其实就是入栈出栈问题：

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // TODO 题目限定只有括号，那么可以把case判断在入栈时候，如果没有，可以用正则替换提取。
  const stack = [];
  for (key of s) {
    switch (key) {
      case '(':
      case '[':
      case '{':
        stack.push(key);
        break;
      case '}':
        if (stack.pop() !== '{') {
          return false;
        }
        break;
      case ']':
        if (stack.pop() !== '[') {
          return false;
        }
        break;
      case ')':
        if (stack.pop() !== '(') {
          return false;
        }
        break;
    }
  }
  if (stack.length) {
    return false;
  }
  return true;
};
console.log(isValid('()[]{}'));

https//programmercarl.com/0020.有效的括号.html

删除字符串中的所有相邻重复项

https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例： 输入："abbaca"  输出："ca"

https://programmercarl.com/1047.删除字符串中的所有相邻重复项.html

逆波兰表达

什么是波兰表达式

我们日常的运算表达式通常为中缀表达式，也就是运算符在运算数的中间，如：a + b * (c - d) + e/f。这种表达式人类很容易识别，并根据其进行计算，但计算机识别这种表达式非常困难。

因此，1920年，波兰科学家扬·武卡谢维奇（Jan ukasiewicz）发明了一种不需要括号的计算表达式的表示法将操作符号写在操作数之前，也就是前缀表达式，即波兰式（Polish Notation, PN）。上述中缀表达式转换为波兰表达式的格式如下：+a+*b-cd/ef

将上面的字母换成具体的数字（1 + 2 * (4 - 3) + 6/2），波兰表达式为：+1+*2-4 3/ 6 2 ，计算方式从右向左扫描

+1+*2-4 3/ 6 2 // 从右向左扫描，当遇到运算符时计算其最近的右侧2个运算数
+1+*2-4 3 3   //先计算最右侧的数据，也就是 6/2=3
+1+*2 1 3     // 同理，4-3 = 1
+1+2 3         // 同理， 2*1= 1
+1+5  
6

上面的运算符和运算数就可以通过通用的数据结构进行计算

什么是逆波兰表达式

运算符在运算数后面的表达式就是逆波兰表达式

波兰表达式也称为前缀表达式，而逆波兰表达式则称为后缀表达式

（1 + 2 * (4 - 3) + 6/2），逆波兰表达式为：1 2  4 3 -*+ 6 2 / +，而计算方式正好相反，也就是从左向右扫描

1 2  4 3 -*+ 6 2 / + //计算方式正好相反，也就是从左向右扫描
1 2 1 *+ 6 2 / +
1 2 + 6 2 / +
3 6 2 / +
3 3 +
6

总结：

• 波兰表示法（Polish notation，或波兰记法）操作符置于操作数的前面，因此也称做前缀表示法。

• 逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法）所有操作符置于操作数的后面，因此也被称为后缀表示法。

逆波兰表达式求值

https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

示例 1：输入：tokens = ["2","1","+","3","*"]      输出：9

解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：输入：tokens = ["4","13","5","/","+"]    输出：6

解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

这个还是比较简单的

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
  const stack = [];
  const op = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => a / b > 0 ? Math.floor(a / b) : Math.ceil(a / b)
  };
  while (tokens.length) {
    const letter = tokens.shift();
    const fun = op[letter];
    if (typeof fun === 'function') {
      const b = stack.pop();
      const a = stack.pop();
      const result = fun(a, b);
      stack.push(result);
    } else {
      stack.push(parseInt(letter, 10));
    }
  }
  return stack.pop();
};

模拟计算器实现

比如((2 + 1) * 3) = 9，如果直接用中缀表达式，需要考虑到 计算的优先级，会非常复杂。

中缀表达式转逆波兰表达式

const str = '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';
const tokens = str.match(/(\d+|\+|\-|\*|\/|\^)/g);
console.log(tokens);
console.log(isNaN('3'));

function infixToPostfix(infixExpression) {
  const precedence = {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2,
    '^': 3,
  };
  const output = [];
  const stack = [];

  // 添加对左括号的支持，右括号不进入precedence因为右括号总是比其他运算符优先级高
  const tokens = infixExpression.match(/(\d+|\+|\-|\*|\/|\^|\(|\))/g);

  for (const token of tokens) {
    const num = parseFloat(token, 10);
    if (!isNaN(num)) { // 数字直接输出
      output.push(token);
    } else if (token === '(') { // 左括号直接入栈
      stack.push(token);
    } else if (token === ')') { // 右括号，弹出直到遇到左括号
      while (stack[stack.length - 1] !== '(') {
        output.push(stack.pop());
      }
      stack.pop(); // 弹出左括号，不加入输出
    } else if (token in precedence) { // 其他运算符
      while (
        stack.length > 0 &&
        precedence[token] <= precedence[stack[stack.length - 1]] &&
        stack[stack.length - 1] !== '('
        ) {
        output.push(stack.pop());
      }
      stack.push(token);
    }
  }

  // 将剩余的运算符（除了左括号）弹出并输出
  while (stack.length > 0 && stack[stack.length - 1] !== '(') {
    output.push(stack.pop());
  }

  return output.join(' ');
}

这样再进行计算，个人感觉都比直接处理中缀表达式简单。

队列

JavaScript 里面没有 优先队列 ，这个需要手动实现。

关于有先队列，还是单独开一篇：《从手搓优先队列实现到leetcode 刷题》

参考文章：

你知道波兰表达式和逆波兰表达式吗 https://zhuanlan.zhihu.com/p/65110137

波兰表达式 & 逆波兰表达式 https://blog.csdn.net/zcs425171513/article/details/118310303

转载本站文章《栈与队列经典题目回顾：​ 有效括号/逆波兰表达》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9100.html