【003】每日算法學習——day3棧

棧，是限定僅在表尾進行插入或删除操作的線性表。是以，對棧來說，表尾端有其特殊的含義，稱為棧頂；相應的，表頭端稱為棧底。不含元素的空表稱為空棧。

棧的特點：後進先出

C++ STL stack的使用方法：

引入：

stack定義在<stack>頭檔案中，需要引入<stack>頭檔案。

​

​#include <stack>​

​

定義棧：

​

​stack<資料類型> 變量名;​

​​ 

例如：​

​stack<char> s;​

​​ ​

​stack<string> str;​

​

基本操作：

入棧：

​

​變量名.push(元素);​

​ 

例如：​

​s.push(x);​

​

出棧：

​

​變量名.pop();​

​

例如：​

​s.pop();​

​

注意：出棧操作僅将棧頂元素删除，并不會傳回棧頂元素。

擷取棧頂元素：

​

​變量名.top();​

​

例如：​

​char ch = s.top();​

​

判斷棧空：

​

​變量名.empty();​

​

例如：​​

​s.empty();​

​ (當棧空是為true，否則為false）

棧的元素個數：

​

​變量名.size();​

​

例如：​

​s.size();​

​ (擷取棧中的元素個數）

Question No.1

有效的括号

​​https://leetcode.cn/problems/valid-parentheses/​​

思路：首先擷取字元串的元素個數，判斷是否是奇數，如果是奇數，直接傳回​

​false​

​；然後建立棧，周遊給定的字元串。如果字元是右括号，我們可以直接将其入棧，否則就需要先判斷棧是否為空，因為先出現左括号注定無法比對；然後判斷字元中的左括号是否和棧頂的右括号比對。比對則繼續，不比對直接傳回​

​false​

​；最後在周遊結束後，判斷棧是否為空，為空傳回​

​true​

​，否則傳回​

​false​

​。

class Solution {
public:
    bool isValid(string s) {
        int n  = s.size();
        if(n % 2 == 1) return false;
        stack<char> str;
        for(char ch : s ){
            if(ch == '(' || ch =='[' || ch == '{') str.push(ch);
            else if(str.size() == 0) return false;
            else if(ch == ')' ){
                if(str.top() != '(') return false;
                else str.pop();
            }else if(ch == ']'){
                if(str.top() != '[') return false;
                else str.pop();
            }else if(ch == '}'){
                if(str.top() != '{') return false;
                else str.pop();
            }
        }
        if(str.size() == 0) return true;
        else return false;
    }
};      

Question No.2

逆波蘭表達式求值

​​https://leetcode.cn/problems/evaluate-reverse-polish-notation/​​

​逆波蘭式：​​https://baike.baidu.com/item/逆波蘭式/128437​​

思路：周遊字元串數組tokens，用字元串最後一位判斷是否是數值（之是以不用第一位判斷是因為存在負數），如果是數值，則使用​

​stoi​

​将字元串轉換為數值。如果不是數值，則擷取上兩個元素取出，進行運算，再将運算得到的新值入棧。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> s;
        for(string& token : tokens){
            if(token[token.size()-1] >= '0' && token[token.size()-1] <= '9'){
                s.push(stoi(token));
            }else{
                long long b = s.top();
                s.pop();
                long long a = s.top();
                s.pop();
                s.push(calc(a,b,token));
            }
        }
        return s.top();
    }

    long long calc(long long a, long long b, string op){
        if(op == "+") return a + b;
        if(op == "-") return a - b;
        if(op == "*") return a * b;
        if(op == "/") return a / b;
        return 0;
    }
};      

Question No.3

#include<iostream>
#include<stack>
using namespace std;

int main()
{
    string s;
    cin >> s;
    stack<char> stack;
    int n = 0; // 記錄可以消除多少對[兩個連續且相同的字母]
    
    for(int i = 0;i < s.size();i++){
        // 如果棧中元素個數大于0，并且目前字元與棧頂元素相同
        if(stack.size() > 0 && s[i] == stack.top()){
            stack.pop();
            n++;
        }else{
            stack.push(s[i]);
        }
    }
    
    if(n % 2 == 1) cout << "Yes";
    else cout << "No";
    
    return 0;
}