当前位置：首页 > news >正文

数据结构之栈和队列——LeetCode：150. 逆波兰表达式求值，224. 基本计算器，232. 用栈实现队列

news 来源：原创 2024/9/27 8:44:17

150. 逆波兰表达式求值

题述

150. 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

运行代码

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> stk;int n = tokens.size();for (int i = 0; i < n; i++) {string& token = tokens[i];if (isNumber(token)) {stk.push(atoi(token.c_str()));} else {int num2 = stk.top();stk.pop();int num1 = stk.top();stk.pop();switch (token[0]) {case '+':stk.push(num1 + num2);break;case '-':stk.push(num1 - num2);break;case '*':stk.push(num1 * num2);break;case '/':stk.push(num1 / num2);break;}}}return stk.top();}bool isNumber(string& token) {return !(token == "+" || token == "-" || token == "*" || token == "/");}
};

代码思路

int evalRPN(vector<string>& tokens)：
- stack<int> stk;：创建一个整数栈，用于存储操作数和中间结果。
- int n = tokens.size();：获取输入的逆波兰表达式字符串数组的长度。
- for (int i = 0; i < n; i++)：遍历输入的字符串数组。
  - string& token = tokens[i];：获取当前遍历到的字符串。
  - if (isNumber(token))：调用 isNumber 函数判断当前字符串是否为数字。如果是数字，则将其转换为整数并推入栈中。使用 atoi(token.c_str()) 将字符串转换为整数。
  - 如果当前字符串不是数字，说明是运算符。从栈中弹出两个操作数 num2 和 num1，注意先弹出的是第二个操作数。然后根据运算符进行相应的运算，并将结果推入栈中。
- return stk.top();：遍历结束后，栈中只剩下最终的结果，返回栈顶元素。
bool isNumber(string& token)：这个函数用于判断输入的字符串是否为数字。通过检查字符串是否不等于 "+"、"-"、"*"、"/" 这四个运算符来确定它是否为数字。如果不是运算符，就认为是数字。
逆波兰表达式的求值原理是：从左到右遍历表达式，如果遇到数字就将其推入栈中；如果遇到运算符，就从栈中弹出两个操作数，进行相应的运算，并将结果推入栈中。重复这个过程，直到遍历完整个表达式。最后，栈中剩下的唯一元素就是表达式的结果。
在这个代码中，使用栈来实现这个求值过程。当遇到数字时，将其转换为整数并推入栈中。当遇到运算符时，从栈中弹出两个操作数，进行相应的运算，并将结果推入栈中。通过这种方式，逐步计算出逆波兰表达式的结果。

224. 基本计算器

题目描述

224. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

运行代码

class Solution {
public:int calculate(string s) {stack<int> ops;ops.push(1);int sign = 1;int ret = 0;int n = s.length();int i = 0;while (i < n) {if (s[i] == ' ') {i++;} else if (s[i] == '+') {sign = ops.top();i++;} else if (s[i] == '-') {sign = -ops.top();i++;} else if (s[i] == '(') {ops.push(sign);i++;} else if (s[i] == ')') {ops.pop();i++;} else {long num = 0;while (i < n && s[i] >= '0' && s[i] <= '9') {num = num * 10 + s[i] - '0';i++;}ret += sign * num;}}return ret;}
};

代码思路

int calculate(string s)：
- stack<int> ops;：创建一个整数栈，用于存储符号。
- ops.push(1);：初始化栈，将初始符号设为正号（1）。
- int sign = 1;：用于表示当前数字的符号。
- int ret = 0;：存储最终的计算结果。
- int n = s.length();：获取输入字符串的长度。
- int i = 0;：用于遍历输入字符串的索引。
- while (i < n)：开始遍历输入字符串。
  - 如果当前字符是空格（' '），直接跳过，继续下一个字符，即 i++。
  - 如果当前字符是加号（'+'），设置当前数字的符号为栈顶符号，即 sign = ops.top();，然后继续下一个字符，即 i++。
  - 如果当前字符是减号（'-'），设置当前数字的符号为栈顶符号的相反数，即 sign = -ops.top();，然后继续下一个字符，即 i++。
  - 如果当前字符是左括号（'('），将当前符号推入栈中，即 ops.push(sign);，然后继续下一个字符，即 i++。
  - 如果当前字符是右括号（')'），弹出栈顶符号，即 ops.pop();，然后继续下一个字符，即 i++。
  - 如果当前字符是数字：
    - long num = 0;：用于存储当前数字。
    - while (i < n && s[i] >= '0' && s[i] <= '9')：当字符是数字时，将其转换为整数累加到 num 中，并继续下一个字符，即 i++。
    - 将当前数字乘以符号累加到结果中，即 ret += sign * num;。
这个算法使用栈来处理括号和符号。当遇到左括号时，将当前符号推入栈中，以便在遇到右括号时恢复之前的符号状态。
通过设置 sign 变量来确定当前数字的符号。当遇到加号或减号时，根据栈顶符号更新 sign。
遍历输入字符串，将数字转换为整数并根据符号累加到结果中。当遇到括号时，使用栈来处理嵌套的表达式。

232. 用栈实现队列

题目描述

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

运行代码

class MyQueue {
private:stack<int> A, B;
public:MyQueue() {}void push(int x) {A.push(x);}int pop() {int peek = this->peek();B.pop();return peek;}int peek() {if (!B.empty())return B.top();if (A.empty()) return -1;while (!A.empty()){B.push(A.top()), A.pop();}int res = B.top();return res;}bool empty() {return A.empty() && B.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

代码思路

stack<int> A, B;：使用两个整数栈 A 和 B 来模拟队列。

MyQueue()：构造函数，用于初始化队列对象，不执行任何操作。
void push(int x)：将元素 x 推入栈 A。这个操作的时间复杂度为。
int pop()：首先调用 peek() 方法获取队首元素。然后从栈 B 中弹出队首元素并返回。这个操作的时间复杂度为（如果需要从栈 A 转移元素到栈 B，则为，其中 n 是当前栈 A 中的元素个数）。
int peek()：
- 如果栈 B 不为空，直接返回栈 B 的栈顶元素，即队首元素。这个操作的时间复杂度为。
- 如果栈 A 为空，返回 -1，表示队列为空。
- 如果栈 B 为空且栈 A 不为空，将栈 A 中的元素逐个弹出并推入栈 B，然后返回栈 B 的栈顶元素。这个操作的时间复杂度为，其中 n 是当前栈 A 中的元素个数。
bool empty()：判断栈 A 和栈 B 是否都为空，如果都为空则返回 true，表示队列为空；否则返回 false。这个操作的时间复杂度为。
入队操作：将元素直接推入栈 A，相当于在队列的尾部添加元素。
出队和查看队首元素操作：如果栈 B 不为空，直接从栈 B 中弹出或查看元素，因为栈 B 的顺序与队列的顺序一致。如果栈 B 为空，将栈 A 中的元素逐个弹出并推入栈 B，这样栈 B 的顺序就与队列的顺序一致了，然后从栈 B 中进行出队或查看队首元素的操作。