代码随想录算法训练营第十一天| 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

题目：20. 有效的括号

文章链接：代码随想录

视频链接：LeetCode:20.有效的括号

题目链接：力扣题目链接

图释：

class Solution {
public:
    // 有效的括号
bool isValid(string s) {
	// 遇到左括号时就放入右括号，遇到右括号时，与栈内的顶元素进行比较
	// 情况一：与栈顶元素相等，则是true
	// 情况二：与栈顶元素不相等，则可能是顺序错误
	// 情况三：栈内元素为空，则说明左括号多了
	// 情况四：数组遍历结果，则说明右括号多了
	stack<char>st;
	for (int i = 0; i < s.size(); i++) {
		//遇到左括号时就放入右括号
		if (s[i] == '(') {
			st.push(')');
		}else if(s[i] == '['){
			st.push(']');
		}else if (s[i] == '{') {
			st.push('}');
		}
		// 遇到右括号时
		if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
			// 先判断栈内元素是否为空
			if (st.empty())return false;
			// 遇到右括号，与栈顶元素进行比较
			if (s[i] == st.top()) {
				st.pop(); // 相等则将栈内元素弹出
			}
			else {
				// 不相等直接返回false
				return false;
			}
		}
	}
	// 数组遍历完，查看栈内元素情况
	if (st.empty())return true;
	return false;
}

};

题目：1047. 删除字符串中的所有相邻重复项

文章链接：代码随想录

视频链接：LeetCode:1047.删除字符串中的所有相邻重复项

题目链接：力扣题目链接

图释：

class Solution {
public:
// 删除字符串中的所有相邻重复项
string removeDuplicates(string s) {
	// 思路：遍历每个元素时，先判断栈内元素是否为空，如果为空则直接放入
	// 如果不为空，则与栈内元素进行比较，如果相同的话，则移除栈内元素，不相同的话也是直接放入
	// 最后，直接输出栈内元素，再进行反转
	stack<char>st;
	for (int i = 0; i < s.size(); i++) {
		if (st.empty() || st.top() != s[i]) {
			st.push(s[i]);
		}
		else {
			// 如果栈顶元素等于当前字符，则弹出栈顶元素
			st.pop();
		}
	}
	// 再把所有元素拿出来
	string result;
	int i = 0;
	while (st.empty() != true) {
		result += st.top(); //使用了string的重载+号
		st.pop();
	}
	reverse(result.begin(), result.end());
	return result;
}
};

题目：150. 逆波兰表达式求值

文章链接：代码随想录

视频链接：LeetCode:150.逆波兰表达式求值

题目链接：力扣题目链接

图释：

class Solution {
public:
    // 逆波兰表达式求值
int evalRPN(vector<string>& tokens) {
	// 用栈来完成，遍历数组放进栈内，当遇到有效运算符时，取出栈顶的两个元素进行运算，再把运算结果放进栈中
	stack<long long>st;
	for (int i = 0; i < tokens.size(); i++) {
		// 如果数组没遍历完，就遇到栈为空，则说明输入错误
		if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
			long long temp1 = st.top();
			st.pop();
			long long temp2 = st.top();
			st.pop();
			long long sum;
			if (tokens[i] == "+") {
				sum = temp1 + temp2;
			}else if (tokens[i] == "-") {
				sum = temp2 - temp1;
			}else if (tokens[i] == "*") {
				sum = temp1 * temp2;
			}else if (tokens[i] == "/") {
				sum = temp2 / temp1;
			}
			st.push(sum);
		}else{
		    st.push(stoll(tokens[i]));
        }
	}
	int result = st.top();
	st.pop();
	return result;
}
};