初解LeetCode之题，每题若新世界。经时方悟，众题多依结构而群，若能识其式，则题自解。今日论栈。
于其前文已述栈之运作。今以是基，解三古题。
所遇之境：
- 三题逐一解之：平衡括号，逆序字符串，简化路径
- 堆栈之用，非止面试之场
简要备忘
后进先出：末入者先出。push加于顶上，pop 降顶。于 JavaScript，数组已具栈之能。若求详尽，则在前文 中详述 。
于此，论其弊。
第一弊：平衡括号
弊状：予一串 s，唯含括号而已。()[]{}，审其可否。每启必有其合，且序当得宜。
例证
Input: "()[]{}" → true
Input: "([)]" → false
Input: "{[]}" → true
吾等何以思之？
"后者启者，先者闭之。"此乃栈之长也。
循文而度。每遇启，则入栈；每逢阖，必应栈顶。若终而栈空，则尽合矣。
解法
function validParentheses(s) {
const stack = [];
const pairs = { ")": "(", "}": "{", "]": "[" };
for (const char of s) {
if (char === "(" || char === "{" || char === "[") {
stack.push(char);
} else if (stack.pop() !== pairs[char]) {
return false;
}
}
return stack.length === 0;
}
要义：
-
pairs每阖必配其启。 - 启入栈中。阖则验之。
pop - 若堆栈为空时
pop，返之undefined然较之则谬矣。安闲，如此则无需复检。 - 终，栈必空。
繁复：時為O(n)，空為O(n)。
第二题：逆序字符串（易）
适变之术也"反转字符串"之LeetCode吾将逆一字，用栈为之。
题曰：予一字符串s，求其逆序字符串。
例证
Input: "stack" → "kcats"
Input: "hello" → "olleh"
吾将何以思之？
"逆"者，入之有序，出之逆序也。此即栈之功用。
于世中，汝将用之s.split("").reverse().join("")吾已备妥。今以栈观其理。
解也
var reverseString = function (s) {
const stack = [...s]; // crea un stack con los caracteres
let reversed = "";
while (stack.length > 0) {
reversed += stack.pop();
}
return reversed;
};
吾等悉将诸字符纳于栈中，复逐一取出之。如pop返其末入者，字反而出。
繁复：時O(n)空O(n)。
第三题：简化路径（中）
简化路径(LeetCode)请提供需要翻译的英文文本。
难题：既得Unix之绝对路径，化其为标准形。
规约：
-
.此乃当前目录。 -
..升一级。 -
//此乃视之如也/. - 其果未终也
/，惟根不除。
例证
Input: "/home//foo/" → "/home/foo"
Input: "/../" → "/"
Input: "/a/./b/../../c/" → "/c"
吾等何以思之？
何所为之？..? 乃返于前所之目录。彼处有标，吾辈当记所经之路，方可回溯。
吾辈启程于径。/吾等遍察诸构件。
-
""哦"."，勿视。 -
".."揭栈顶之极。 - 凡他物皆为目录，入栈而去。
终，栈含简路之目录。
解也
var simplifyPath = function (path) {
const stack = [];
for (const part of path.split("/")) {
if (part === "" || part === ".") continue;
if (part === "..") stack.pop();
else stack.push(part);
}
return "/" + stack.join("/");
};
谨示：于JavaScript，pop临空栈，无有损焉，惟返undefined耳。是故，若径途欲升越本根，则无需复加验之。
难易：时若O(n)，地亦O(n)。
三者之理，其趣何在？
若续读之，当见同此。三者皆解本源之同题，可返归旧境。
- 平衡括号：记其末启，以验其合。
- 逆序字符串：返其逆序之序。
- 简化路径：
..返归一阶。
此乃栈之奇能。凡遇难题，嘱汝忆其末，撤其失，或逆序而理，其策几莫不归栈。
栈之用，不止面试
栈非面试之戏言。凡"返"之理，遍现于世：
- 浏览器之"后退"钮，即栈也。
- 编辑器之"撤销/重做"，亦然。
- 诸语言之调用栈（是故有栈溢出之误）。
- 数据之管道，须存所睹之境。
为续习之故
力扣难题之题：
何者使君费思最多？请留言告知。吾则觉简化路径题，颇费周折。