每日算法刷题Day56:7.31:leetcode 栈6道题，用时2h30min

五.表达式解析

1.套路

1.中缀表达式:"操作数① 运算符② 操作数③" 的顺序，运算符在两个操作数中间。
(1)求解没有括号 的中缀表达式
可以用一句顺口溜来概括：遇到乘除立即算，遇到加减先入栈。

• 「乘除立即算」的含义是把栈顶元素和当前元素进行 * 或者 / 的计算
• 「加减先入栈」的含义是如果当前操作符是 + 则直接把当前数字进栈，如果当前操作符是 - 则把当前数字取反(技巧) 放入到栈中。
  最后将栈中元素求和就是表达式的值。
  所以是遇到当前数字根据前面操作符来判断操作，所以得提前知道前面的操作符，需要一个变量存储
  2.逆波兰表达式，也叫做后缀表达式。
  后缀表达式是 "操作数① 操作数③ 运算符②" 的顺序，运算符在两个操作数之后。
  对后缀表达式求值的过程是：
• 如果遇到数字就进栈；
• 如果遇到操作符，就从栈顶弹出两个数字分别为 num2（栈顶）、num1（栈中的第二个元素）；计算 num1 运算符 num2 .

3,嵌套括号，需要从内向外生成与拼接字符串,想到栈[[六.栈#3. 394. 字符串解码(中等,学习)]] [[六.栈#4. 224. 基本计算器(困难)]][[六.栈#6. 726. 原子的数量(困难)]]

2.题目描述

1(学习).通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。
相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。
例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。
另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。
实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘(答案)。
2.给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数(答案)。
注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示
  3(重点学习).给定一个经过编码的字符串，返回它解码后的字符串(答案)。
  编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
  你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
  此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
  4.给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
  注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
  5.给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
  整数除法仅保留整数部分。
  你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
  注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
  6.给你一个字符串化学式 formula ，返回 每种原子的数量(答案) 。
  原子总是以一个大写字母开始，接着跟随 0 个或任意个小写字母，表示原子的名字。
  如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。
• 例如，"H2O" 和 "H2O2" 是可行的，但 "H1O2" 这个表达是不可行的。
  两个化学式连在一起可以构成新的化学式。
• 例如 "H2O2He3Mg4" 也是化学式。
  由括号括起的化学式并佐以数字（可选择性添加）也是化学式。
• 例如 "(H2O2)" 和 "(H2O2)3" 是化学式。
  返回所有原子的数量，格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。

3.学习经验

1.弄懂[[六.栈#3. 394. 字符串解码(中等,学习)]]

1. 1006. 笨阶乘(中等,学习)

1006. 笨阶乘 - 力扣（LeetCode）

思想

1.通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。
相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。
例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。
另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。
实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。
2.- 我们平时见到的运算表达式是 中缀表达式，即 "操作数① 运算符② 操作数③" 的顺序，运算符在两个操作数中间。
求解没有括号的中缀表达式的时候，可以用一句顺口溜来概括：遇到乘除立即算，遇到加减先入栈。

• 「乘除立即算」的含义是把栈顶元素和当前元素进行 * 或者 / 的计算
• 「加减先入栈」的含义是如果当前操作符是 + 则直接把当前数字进栈，如果当前操作符是 - 则把当前数字取反放入到栈中。
  最后将栈中元素求和就是表达式的值

代码

class Solution {
public:int clumsy(int n) {int res = 0;vector<int> stk;stk.push_back(n);for (int i = n - 1; i >= 1; --i) {int op = (n - i - 1) % 4;switch (op) {case 0:stk.back() *= i;break;case 1:stk.back() /= i;break;case 2:stk.push_back(i);break;default:stk.push_back(-i);}}for (int& x : stk)res += x;return res;}
};

2. 150. 逆波兰表达式求值(中等)

150. 逆波兰表达式求值 - 力扣（LeetCode）

思想

1.给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示
  2.逆波兰表达式，也叫做后缀表达式。
  后缀表达式是 "操作数① 操作数③ 运算符②" 的顺序，运算符在两个操作数之后。
  对后缀表达式求值的过程是：
• 如果遇到数字就进栈；
• 如果遇到操作符，就从栈顶弹出两个数字分别为 num2（栈顶）、num1（栈中的第二个元素）；计算 num1 运算符 num2 .

代码

class Solution {
public:int evalRPN(vector<string>& tokens) {int n = tokens.size();vector<int> stk;for (int i = 0; i < n; ++i) {string s = tokens[i];if (s == "*") {int t = stk.back();stk.pop_back();stk.back() *= t;} else if (s == "/") {int t = stk.back();stk.pop_back();stk.back() /= t;} else if (s == "+") {int t = stk.back();stk.pop_back();stk.back() += t;} else if (s == "-") {int t = stk.back();stk.pop_back();stk.back() -= t;} elsestk.push_back(stoi(s));}return stk.back();}
};

3. 394. 字符串解码(中等,学习)

394. 字符串解码 - 力扣（LeetCode）

思想

1.给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
2.本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。
3.首先需要两个变量和一个栈，变量num记录当前嵌套深度的重复次数,变量 res记录当前嵌套深度的字符串(进入新深度置0，回到旧深度与之前字符串拼接，最终只有一个深度，所以也是最终答案),栈记录一对元素，为num,前一嵌套深度字符串pre,所以算法流程如下:

• c是数字，更新当前嵌套深度字符串res,在后面拼接
• c是[.新的嵌套深度，所以num和res进栈，然后置0
• c是],当前嵌套深度结束，取出栈顶元素num和pre,更新当前嵌套深度字符串res=pre+res*num
• c是数字，更新num
  <![[字符串解码1.png]],![[字符串解码2.png]],![[字符串解码3.png]]
  ,![[字符串解码4.png]]
  ，![[字符串解码5.png]]
  ,![[字符串解码6.png]]
  ，![[字符串解码7.png]]
  ,![[字符串解码8.png]]

代码

class Solution {
public:typedef pair<int, string> PIS;string decodeString(string s) {int n = s.size();vector<PIS> stk; // [前数组和之前字符串prestring res = ""; // 当前[]内的字符串int num = 0;for (int i = 0; i < n; ++i) {if (s[i] >= 'a' && s[i] <= 'z') {res += s[i];} else if (s[i] == '[') {stk.push_back({num, res});res = "";num = 0;} else if (s[i] == ']') {auto t = stk.back();int k = t.first;string pre = t.second;stk.pop_back();string tmp = "";for (int j = 0; j < k; ++j)tmp += res;res = pre + tmp;} elsenum = num * 10 + s[i] - '0';}return res;}
};

4. 224. 基本计算器(困难)

224. 基本计算器 - 力扣（LeetCode）

思想

1.给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
2.跟[[六.栈#3. 394. 字符串解码(中等,学习)]]一样，都要涉及深层嵌套与前一层的拼接
3.但这一题比较坑的是有空格，所以一开始记得要用erase+remove把空格删去

代码

class Solution {
public:typedef long long ll;typedef pair<int, ll> PII;int calculate(string s) {ll res = 0;vector<PII> stk; // op,pre// 还有空格，真坑s.erase(remove(s.begin(), s.end(), ' '), s.end());int n = s.size();for (int i = 0; i < n; ++i) {if (s[i] == '(') {if (i > 0 &&s[i - 1] =='-') // 负号就这一种情况，正号情况多，可以i==0,可以前面是正号，可以前面是嵌套括号stk.push_back({-1, res});elsestk.push_back({1, res});res = 0;} else if (s[i] == ')') {auto t = stk.back();stk.pop_back();int op = t.first;ll pre = t.second;res = pre + op * res;} else if (s[i] >= '0' && s[i] <= '9') {int op = 1;if (i > 0 && s[i - 1] == '-')op = -1;int j = i + 1;ll tmp = s[i] - '0';while (j < n && s[j] >= '0' && s[j] <= '9') {tmp = tmp * 10 + s[j] - '0';++j;}// [i,j)res += op * tmp;i = j - 1;}}return res;}
};

5. 227. 基本计算机II(中等)

227. 基本计算器 II - 力扣（LeetCode）

思想

1.给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
**注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
2.跟[[六.栈#1. 1006. 笨阶乘(中等,学习)]]一样都是不含括号的中缀表达式，所以我得预先知道数字前面的操作符,所以用过变量op存储，然后得到整段数字，根据前面操作符进行加减入栈，乘除更新栈顶

代码

class Solution {
public:typedef long long ll;int calculate(string s) {s.erase(remove(s.begin(), s.end(), ' '), s.end());int n = s.size();vector<int> stk;ll res = 0;int op = 0;for (int i = 0; i < n; ++i) {if (s[i] == '+')op = 0;else if (s[i] == '-')op = 1;else if (s[i] == '*')op = 2;else if (s[i] == '/')op = 3;else {ll num = s[i] - '0';int j = i + 1;while (j < n && s[j] >= '0' && s[j] <= '9') {num = num * 10 + s[j] - '0';++j;}i = j - 1;if (op == 0)stk.push_back(num);else if (op == 1)stk.push_back(-num);else if (op == 2)stk.back() *= num;elsestk.back() /= num;}}for (int& x : stk)res += x;return res;}
};

6. 726. 原子的数量(困难)

726. 原子的数量 - 力扣（LeetCode）

思想

1.给你一个字符串化学式 formula ，返回 每种原子的数量 。
原子总是以一个大写字母开始，接着跟随 0 个或任意个小写字母，表示原子的名字。
如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。

• 例如，"H2O" 和 "H2O2" 是可行的，但 "H1O2" 这个表达是不可行的。
  两个化学式连在一起可以构成新的化学式。
• 例如 "H2O2He3Mg4" 也是化学式。
  由括号括起的化学式并佐以数字（可选择性添加）也是化学式。
• 例如 "(H2O2)" 和 "(H2O2)3" 是化学式。
  返回所有原子的数量，格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。
  2.此题跟[[六.栈#3. 394. 字符串解码(中等,学习)]]类似，只不过这次数字在后面，不是在遇到(的时候存，而是在遇到)的时候往后遍历获取，然后栈中元素就是一个哈希表，遇到)首先获取次数，然后得到栈顶pre,然后更新当前嵌套哈希表为res+pre*num
  3.注意得到哈希表转换为答案时，次数1不用放进去

代码

class Solution {
public:string countOfAtoms(string formula) {int n = formula.size();map<string, int> res;vector<map<string, int>> stk;for (int i = 0; i < n; ++i) {if (formula[i] == '(') {stk.push_back(res);res.clear();} else if (formula[i] == ')') {int num = 0;int j = i + 1;while (j < n && formula[j] >= '0' && formula[j] <= '9') {num = num * 10 + formula[j] - '0';++j;}i = j - 1;if (num == 0)num = 1;auto pre = stk.back();stk.pop_back();for (auto t : res) {pre[t.first] += num * t.second;}res = pre;} else {string tmp = "";tmp += formula[i];int j = i + 1;while (j < n && formula[j] >= 'a' && formula[j] <= 'z') {tmp += formula[j];++j;}int num = 0;while (j < n && formula[j] >= '0' && formula[j] <= '9') {num = num * 10 + formula[j] - '0';++j;}i = j - 1;if (num == 0)num = 1;res[tmp] += num;}}string ans = "";for (auto t : res) {ans += t.first;if (t.second > 1)ans += to_string(t.second); // 没有1}return ans;}
};