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

LeetCode 20有效的括号

题目链接：20.有效的括号

//左括号直接入栈，写的代码比较繁琐
class Solution {
public:
	bool isValid(string s) {
		stack<char> st;
		for (char c : s) {
			if (c == '(' || c == '[' || c == '{') st.push(c);
			else if (c == ')') {
				if (st.empty() || st.top() == '[' || st.top() == '{') return false;
				//st.top() == '('
				else st.pop();
			}
			else if (c == ']') {
				if (st.empty() || st.top() == '(' || st.top() == '{') return false;
				//st.top() == '['
				else st.pop();
			}
			else if (c == '}') {
				if (st.empty() || st.top() == '[' || st.top() == '(') return false;
				//st.top() == '{'
				else st.pop();
			}
		}
		return st.empty();
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//入栈右括号，代码简洁
class Solution {
public:
	bool isValid(string s) {
		if (s.size() % 2 != 0) return false;
		stack<char> st;
		for (char c : s) {
            //在匹配左括号的时候，将相应的右括号入栈
			if (c == '(') st.push(')');
			else if (c == '[') st.push(']');
			else if (c == '{') st.push('}');
            //只需要比较当前元素和栈顶元素是否相等即可
			else if (st.empty() || st.top() != c) return false;
			else st.pop();
 		}
		return st.empty();
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

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

//用栈
class Solution {
public:
	string removeDuplicates(string s) {
		stack<char> st;
		for (char c : s) {
			if (st.empty() || c != st.top()) st.push(c);
			else st.pop();
		}
		string ans = "";
		while (!st.empty()) {
			ans += st.top();
			st.pop();
		}
		reverse(ans.begin(), ans.end());
		return ans;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//用字符串直接做栈，省去了最后出栈又反转的功夫
class Solution {
public:
	string removeDuplicates(string s) {
		string ans = "";
		for (char c : s) {
			if (ans.empty() || c != ans.back()) ans.push_back(c);
			else ans.pop_back();
		}
		return ans;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 150逆波兰表达式求值

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

class Solution {
public:
	int evalRPN(vector<string>& tokens) {
		stack<int> st;
		for (string s : tokens) {
			if (s == "+" || s == "-" || s == "*" || s == "/") {
				int num2 = st.top(); st.pop();
				int num1 = st.top(); st.pop();
				if (s == "+") st.push(num1 + num2);
				if (s == "-") st.push(num1 - num2);
				if (s == "*") st.push(num1 * num2);
				if (s == "/") st.push(num1 / num2);
			}
			else {
				//string转为int操作，三步都不能省
				int num = 0;
				istringstream ss(s);
				ss >> num;
				st.push(num);
			}
		}
		return st.top();
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24