---
# System prepended metadata

title: 給小芃睿的(後面有東西)

---

# 給小芃睿的(後面有東西)
會常用到的總共有四個功能
push、top、pop、empty
## Sol1:
```cpp=
#include<stack>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
int main()
{
    int n;
    stack <char> st1;
    string s;
    while(cin >> n)
    {
        getchar();
        for(int i = 0; i < n; i ++)
        {
            getline(cin,s);
            while (!st1.empty())
            {
                st1.pop();
            }
            int l = s.length();
            for (int j = 0; j < l; j ++)
            {
                if (st1.empty())
                {
                    st1.push(s[j]);
                    continue;
                }
                if (st1.top() == '(')
                {
                    if (s[j] == ')')
                    {
                        st1.pop();
                        continue;
                    }
                }
                if (st1.top() == '[')
                {
                    if (s[j] == ']')
                    {
                        st1.pop();
                        continue;
                    }
                }
                st1.push(s[j]);
            }
            if (st1.empty()) cout <<"Yes"<<endl;
            else cout <<"No"<<endl;
        }
    }
}



```
## Sol2:
```cpp=
#include <bits/stdc++.h>
int main()
{
    char in[210], ch[7]="([{)]}";
    int S[210], top; // stack
    while (scanf("%s",in)!=EOF)
    {
        top=-1; // clear stack
        int len=strlen(in);
        assert(len<=150);
        bool error=false;
        for (int i=0; i<len; i++)
        {
            int k=strchr(ch,in[i])-ch;
//or using: for (k=0; k<6 && ch[k]!=in[i]; k++);
            assert(k<6); // no invalid char
            if (k<3) // left
                S[++top]=k; // push
            else
            {
                if (top<0 || k!=S[top]+3)   //mismatch
                {
                    error=true;
                    break;
                }
                top--; // pop
            }
        }
        if (top>=0) error=true;
        printf((error)?"no\n":"yes\n");
    }
    return 0;
}

```
## 439-Knight Moves 
筆記:
BFS
用陣列紀錄可能的移動位置
為了把兩個變數存入queue用pair
```cpp=
#include<iostream>
#include<queue>
#include<string.h>
#define N 8
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
    int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
    int step[10][10];
    char first_char, sce_char;
    int first_int, sce_int;
    while(cin >> first_char >> first_int >> sce_char >> sce_int)
    {
        memset(step,-1,sizeof(step));
        queue <pair<int,int> > q;
        int red_row = sce_int;
        int red_col = sce_char - 96;
        pair <int,int> start = make_pair(first_int,first_char-96);
        q.push(start);
        step[first_int][first_char-96] = 0;
        while(!q.empty())
        {
            pair <int, int> cur = q.front();
            q.pop();
            int row = cur.first;
            int col = cur.second;
            if (row == red_row && col == red_col)
            {
                cout <<"To get from "<<first_char<<first_int<< " to "<<sce_char<<sce_int<<" takes "<<step[row][col]<<" knight moves."<<endl;
                break;
            }
            for(int i = 0; i < 8; i ++)
            {
                int new_row = row + dx[i];
                int new_col = col + dy[i];
                if (new_row < 1 || new_col < 1 ||new_col > N|| new_row > N) continue;
                if (step[new_row][new_col] != -1) continue;
                step[new_row][new_col] = step[row][col]+1;
                pair <int, int> next = make_pair(new_row, new_col);
                q.push(next);
             }
        }
    }
}
```