// 演算法：純模擬。維護一個夠大的字元緩衝區 result 與長度 len，
//        逐字處理 s：字母 append、'*' 刪尾、'#' 複製加倍、'%' 就地反轉。
// Algorithm: pure simulation. Keep a large enough buffer `result` and a length
//        `len`; for each char: letter -> append, '*' -> pop, '#' -> double, '%' -> reverse.

#include <stdlib.h>   // malloc / free
#include <string.h>   // strlen, memcpy

char* processStr(char* s) {
    int n = strlen(s);                       // n = s 的長度 / length of input s

    // '#' 最多把長度加倍；20 個字元最壞情況下長度可達 2^20。
    // '#' doubles length; with up to 20 chars the worst case is 2^20.
    // 多 +1 是為了結尾的 '\0'。 The +1 is room for the terminating '\0'.
    int cap = (1 << 20) + 1;                  // 1<<20 是位元左移，等於 2 的 20 次方 / 1<<20 == 2^20
    char* result = (char*)malloc(cap);        // 向系統要一塊記憶體 / request a buffer from the heap

    int len = 0;                              // result 目前的字元數 / current length of result

    for (int i = 0; i < n; i++) {             // 從左到右掃過 s / scan s left to right
        char c = s[i];                        // 取出第 i 個字元 / current character

        if (c == '*') {                       // 刪除最後一個字元 / remove last char
            if (len > 0) len--;               // 只在非空時減；不需真的清除位元組 / only if non-empty
        } else if (c == '#') {                // 複製整個 result 接在後面 / duplicate result
            // 把前 len 個字元複製到 result+len 起的位置 / copy first len chars onto the tail
            memcpy(result + len, result, len);// memcpy(dst, src, bytes)：複製 len 個位元組 / copy len bytes
            len *= 2;                          // 長度變兩倍 / length doubles
        } else if (c == '%') {                // 就地反轉前 len 個字元 / reverse in place
            int l = 0, r = len - 1;           // 左右兩個索引 / two indices from the ends
            while (l < r) {                   // 往中間靠攏直到相遇 / move inward until they meet
                char t = result[l];           // 暫存左邊字元 / temp save left char
                result[l] = result[r];        // 左邊放右邊的值 / left gets right
                result[r] = t;                // 右邊放暫存的值 / right gets the temp
                l++; r--;                     // 兩端各往中間移一格 / step both indices inward
            }
        } else {                              // 否則是小寫字母 / otherwise it's a lowercase letter
            result[len] = c;                  // 寫到下一個空位 / write at the next free slot
            len++;                            // 長度加一 / length grows by one
        }
    }

    result[len] = '\0';                       // C 字串以 '\0' 結尾 / C strings are NUL-terminated
    return result;                            // 回傳這塊 malloc 的記憶體 / return the malloc'd buffer
}