目錄

一、（leetcode 20）有效的括號

二、（leetcode 1047）刪除字符串中的所有相鄰重復(fù)項

用棧存放?

將字符串直接當成棧?

三、（leetcode 150）逆波蘭表達式求值

---

一、（leetcode 20）有效的括號

力扣題目鏈接

狀態(tài)：已AC，列好所有情況就容易了

三種情況會出現(xiàn)不匹配的情況

1. 
2. 
3. 

class Solution {
public:bool isValid(string s) {if (s.size() % 2 != 0) return false;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(']');else if(st.empty()||st.top()!=s[i])return false;else st.pop();}return st.empty();}
};

二、（leetcode 1047）刪除字符串中的所有相鄰重復(fù)項

力扣題目鏈接

狀態(tài)：已AC

用棧存放?

class Solution {
public:string removeDuplicates(string S) {stack<char> st;for(char t:S){if(st.empty()||t!=st.top()){st.push(t);}else{st.pop();}}string result = "";while (!st.empty()) { // 將棧中元素放到result字符串匯總result += st.top();st.pop();}reverse(result.begin(),result.end());return result;}
};

將字符串直接當成棧?

class Solution {
public:string removeDuplicates(string S) {string result;for(char s : S) {if(result.empty() || result.back() != s) {result.push_back(s);}else {result.pop_back();}}return result;}
};

三、（leetcode 150）逆波蘭表達式求值

力扣題目鏈接

狀態(tài)：已AC

思路：遇到數(shù)字則入棧；遇到運算符則取出棧頂兩個數(shù)字進行計算，并將結(jié)果壓入棧中

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {int num1 = st.top();st.pop();int num2 = st.top();st.pop();if (tokens[i] == "+") st.push(num2 + num1);if (tokens[i] == "-") st.push(num2 - num1);if (tokens[i] == "*") st.push(num2 * num1);if (tokens[i] == "/") st.push(num2 / num1);} else {st.push(stoll(tokens[i]));}}int result = st.top();st.pop(); // 把棧里最后一個元素彈出（其實不彈出也沒事）return result;}
};