20. 有效的括號
題目鏈接：
https://leetcode.cn/problems/valid-parentheses/
思考：
用棧進行存儲，碰到左括號加入，右括號進行判斷
代碼：
class Solution {
public:
? ? bool isValid(string s) {
? ? ? ? stack<char> kuohao;
? ? ? ? int len = s.size();
? ? ? ? for(int i=0;i<len;i++)
? ? ? ? {
? ? ? ? ? ? char c = s[i];
? ? ? ? ? ? if( c == '(' or c == '{' or c == '[')
? ? ? ? ? ? {
? ? ? ? ? ? ? ? kuohao.push(c);
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(kuohao.empty())
? ? ? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? ? ? char top = kuohao.top();
? ? ? ? ? ? ? ? if(c == ')' && top != '(')
? ? ? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? ? ? if(c == '}' && top != '{')
? ? ? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? ? ? if(c == ']' && top != '[')
? ? ? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? ? ? kuohao.pop();
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(kuohao.empty())
? ? ? ? {
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? else
? ? ? ? ? ? return false;
? ? }
};
1047. 刪除字符串中的所有相鄰重復項
題目：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
思路：
?？梢杂脕斫鉀Q這種消除匹配的問題。
來一個字符，判斷棧頂元素是否相同，相同則彈出，并且該元素不加入，否則加入。
代碼：
class Solution {
public:
? ? string removeDuplicates(string s) {
? ? ? ? stack<char> xiaoxiaole;
? ? ? ? int len = s.size();
? ? ? ? for(int i=0;i<len;i++)
? ? ? ? {
? ? ? ? ? ? bool flag = 0;
? ? ? ? ? ? while(!xiaoxiaole.empty() && xiaoxiaole.top() == s[i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cout<<"消除："<<xiaoxiaole.top()<<endl;
? ? ? ? ? ? ? ? xiaoxiaole.pop();
? ? ? ? ? ? ? ? flag=1;
? ? ? ? ? ? }
? ? ? ? ? ? if(flag==0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cout<<"加入:"<<s[i]<<endl;
? ? ? ? ? ? ? ? xiaoxiaole.push(s[i]);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int size = xiaoxiaole.size();
? ? ? ? string new_s;
? ? ? ? new_s.resize(size);
? ? ? ? while(size--)
? ? ? ? {
? ? ? ? ? ? new_s[size] = xiaoxiaole.top();
? ? ? ? ? ? xiaoxiaole.pop();
? ? ? ? }
? ? ? ? return new_s;
? ? }
};
150. 逆波蘭表達式求值
題目：
https://leetcode.cn/problems/evaluate-reverse-polish-notation/
思路：
使用棧解決。
遇到運算符，彈出棧頂兩個元素進行計算，把加入入棧
否則直接入棧。
代碼：
class Solution {
public:
? ? int evalRPN(vector<string>& tokens) {
? ? ? ? stack<int> s;
? ? ? ? int len = tokens.size();
? ? ? ? for(int i=0;i<len;i++)
? ? ? ? {
? ? ? ? ? ? string top = tokens[i];
? ? ? ? ? ? if(top != "+" && top != "-" && top != "*" && top!="/")
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int? input = stoll(top);
? ? ? ? ? ? ? ? s.push(input);
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int token1 = s.top();
? ? ? ? ? ? ? ? s.pop();
? ? ? ? ? ? ? ? int token2 = s.top();
? ? ? ? ? ? ? ? s.pop();
? ? ? ? ? ? ? ? int res;
? ? ? ? ? ? ? ? if(top=="+") s.push(token2+token1);
? ? ? ? ? ? ? ? if(top=="-") s.push(token2-token1);
? ? ? ? ? ? ? ? if(top=="*") s.push(token2*token1);
? ? ? ? ? ? ? ? if(top=="/") s.push(token2/token1);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return s.top();
? ? }
};
