---
# System prepended metadata

title: 資結1115作業小分享><
tags: [CPP]

---

---
title: HackMD Dark Theme
tags: theme
description: Use `{%hackmd theme-dark %}` syntax to include this theme.
---

<style>

html, body, .ui-content {
    background-color: #333;
    color: #ddd;
}

.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
    color: #ddd;
}

.markdown-body h1,
.markdown-body h2 {
    border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
    color: #fff;
}

.markdown-body img {
    background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
    color: white;
    border-left: 2px solid white;
}

.expand-toggle:hover, 
.expand-toggle:focus, 
.back-to-top:hover, 
.back-to-top:focus, 
.go-to-bottom:hover, 
.go-to-bottom:focus {
    color: white;
}


.ui-toc-dropdown {
    background-color: #333;
}

.ui-toc-label.btn {
    background-color: #191919;
    color: white;
}

.ui-toc-dropdown .nav>li>a:focus, 
.ui-toc-dropdown .nav>li>a:hover {
    color: white;
    border-left: 1px solid white;
}

.markdown-body blockquote {
    color: #bcbcbc;
}

.markdown-body table tr {
    background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
    background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
    color: #eee;
    background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
    color: #5EB7E0;
}

</style>

# [C_DT06-易] 中序轉後序
----------------------

### 題目給的範例可以發現，越左邊的運算子會越早被處理，所以要用一個 stack 來把所有的運算子儲存下來處理

**遇到運算元的話就直接輸出**

1. 遇到刮號
   - 右刮號的話把 stack.top() push 進 answer 直到上一個左刮號的運算子
   - 左刮號直接 push 進 stack 裡
1. 遇到乘除
   - 如果現在 stack 最上面的運算子優先級 **大於等於** 乘除，就 stack.top()，因為他們應該要在現在處理的運算子前先被處理，再把目前的運算子 push 進 stack
   - 如果沒有，直接把現在的運算子放入 stack
1. 遇到加減
   - 與乘除一樣
-------------------------------

```cpp
#include <bits/stdc++.h>

using namespace std;

signed main() {
    int n;
    string str, ch;
    cin >> n;
    while(n--){
        while(getline(cin,str)){
            stack <string> st;
            vector <string> ans;
            stringstream ss; ss << str; 
            while(ss >> ch) {
                if(ch == ")") {
                    while(st.top() != "(") {
                        ans.push_back(st.top());
                        st.pop();
                    }
                    st.pop();
                }else if(ch == "(") {
                    st.push("(");
                }else if(ch == "*" || ch == "/") {
                    while(!st.empty() && (st.top() == "*" || st.top() == "/")) {
                        ans.push_back(st.top());
                        st.pop();
                    } 
                    st.push(ch);
                }else if(ch == "+" || ch == "-") {
                    while(!st.empty() && (st.top() == "*" || st.top() == "/" || st.top() == "+" || st.top() == "-")) {
                        ans.push_back(st.top());
                        st.pop();
                    } 
                    st.push(ch);
                }else{
                    ans.push_back(ch);
                }
            }
            
            while(!st.empty()){
                ans.push_back(st.top());
                st.pop();
            }
            for(int i = 0; i < ans.size(); ++i){
                cout << ans[i] << " \n"[i == ans.size()-1]; //這是競程選手蠻常用的寫法，但我很久沒用忘記了，有興趣可以去了解一下
            }
        }
    }
}
```
### 下面這寫法的連結:[" \n"[i == ans.size()-1];](https://stackoverflow.com/questions/30888851/what-does-cout-na-n-do)


-----------------------------
# [C_DT18-] 後序運算式求值

-----------------------------

## 第二題就沒這題要寫得那麼多了

**沒有括號所以很簡單**

### 利用迴圈找到連續的 _運算元 運算元 運算子_ 再push進去stack

-------------------------
```cpp
#include <bits/stdc++.h>

using namespace std;

signed main(){
    string str;
    stack <int> st;
    while(cin >> str){
        if(str == "+" || str == "-" || str == "*" || str == "/" || str == "%"){
            int sec = st.top(); st.pop();
            int ft = st.top(); st.pop();
            if(str == "+") st.push(ft + sec);
            else if(str == "-") st.push(ft - sec);
            else if(str == "*") st.push(ft * sec);
            else if(str == "/") st.push(ft / sec);
            else st.push(ft%sec);
        }else{
            st.push(stoi(str));
        }
    }
    cout << st.top() << '\n';
}
```
----------------------
# [C_BT08-中] 迷宮路徑

## 我覺得很廢沒甚麼要說明的

```cpp
#include <bits/stdc++.h>
using namespace std;

bool isExist(const vector<vector<int>>& maze, int x, int y, int n) {
    return x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 0;
}

bool findPath(vector<vector<int>>& maze, int x, int y, int n, vector<vector<int>>& path) {
    if (x == n - 2 && y == n - 2) {
        path[x][y] = 1;
        return true;
    }
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (isExist(maze, nx, ny, n)) {
            maze[nx][ny] = 2; 
            if (findPath(maze, nx, ny, n, path)) {
                path[nx][ny] = 1;
                return true;
            }
            maze[nx][ny] = 3; 
        }
    }
    return false;
}

signed main(){
    int n;
    cin >> n;
    vector<vector<int>> maze(n, vector<int>(n));
    vector<vector<int>> path(n, vector<int>(n, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> maze[i][j];
        }
    }

    if(findPath(maze, 1, 1, n, path)) {
        path[1][1] = 1;
        for(int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if(path[i][j] == 1) cout << "#";
                else if (maze[i][j] == 3) cout << "*";
                else if (maze[i][j] == 1) cout << "1";
                else cout << "0";
                if(j < n - 1) cout << " ";
            }
            cout << '\n';
        }
    }
}
```