目的: 引導學員學習 regular expression 及 socket 程式設計
作答表單
測驗 1
LeetCode 10. Regular Expression Matching 要求判定給定兩個字串 s 與 p 是否匹配 (match)，要考慮到特殊符號 . 與 *:
- 符號
. 可對應各種字元
- 符號
* 代表前方字元可使用各種數量 (包含 0 個)，例如 p = "a*";，則無論 s 為空字串或者任意個 'a' 組成，均可傳回 true
比對樣式的每個字元作為一個狀態 (包含 . 任何字元)，串接為成單一路線的狀態，最後是結束狀態。
ab.d 所建立的狀態機
輸入字串從起始狀態開始判斷，沿著路線走到結束狀態，每個狀態從輸入字串取一個字元跟該狀態的字元比較，若不匹配則 isMatch 直接判斷失敗，若符合則消耗該字元，把剩下的輸入字串丟到下一個狀態繼續比較。若成功走到結束狀態，且輸入字串已全部被消耗完，則 isMatch 判斷成功
狀態機消耗輸入字串 s 的示意圖，只有在最上面的狀況，消耗所有的輸入字串字元，才算 isMatch = true
考慮到 * 符號，包含零個或是多個字元，在這個狀態中不一定只消耗單一字元，因此需要特別處理，根據可輸入字串的資料，消耗一個到多個該狀態處理的字元，剩下的輸入字串移送到下個狀態再比較。
考慮 * 符號的特別處理，進入到 'c' 狀態的輸入字串為 'ccc'，考慮消耗各種可能，將 'ccc', 'cc', 'c', 及 '∅' 移送到下個狀態進行判斷
以下程式碼為 LeetCode 10. Regular Expression Matching 的一個可能實作:
透過動態規劃，重寫為不需要遞迴呼叫的實作:
請補完程式碼，使得其執行符合 LeetCode 預期並通過給定的測試資料。
作答區
EXP1 = ?
(a) m[i] && (s[i] == c || c == '.')(b) m[i - 1] && (s[i - 1] == c || c == '.')(c) m[i - 1] && (s[i] == c || c == '.')(d) m[i] || (m[i - 1] && (s[i - 1] == c || c == '.'))
EXP2 = ?
(a) m[i] && (s[i] == c || c == '.')(b) m[i - 1] && (s[i - 1] == c || c == '.')(c) m[i - 1] && (s[i] == c || c == '.')(d) m[i] || (m[i - 1] && (s[i - 1] == c || c == '.'))
測驗 2
請詳閱 LeetCode 468. Validate IP Address 題目要求，再考慮以下可能的實作:
請補完程式碼，使得執行符合 LeetCode 預期並通過給定的測試資料。
作答區
COND1 =
(a) runner - walker > 4(b) runner - walker > 5(c) runner - walker > 6(d) runner - walker > 7
COND2 =
(a) size > 4(b) size > 5(c) size > 6(d) size > 7
COND3 =
(a) runner - walker <= 4(b) runner - walker <= 5(c) runner - walker <= 6(d) runner - walker <= 7
COND4 = ?
(a) size == 4(b) size == 5(c) size == 6(d) size == 7
測驗 3
給定檔案 index.html，其內容如下:
今有一個 Linux 環境之下的 C 程式 (server.c) 可讀取 index.html 的內容，並傾聽 port 55688，待網頁瀏覽器連線後，顯示 index.html 的內容。
程式碼如下:
#include <errno.h>
#include <fcntl.h>
#include <netdb.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/epoll.h>
#include <sys/sendfile.h>
#include <sys/socket.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
#define PORT "55688"
#define MAX_EVENTS 5
static int lfd, efd;
static struct epoll_event events[MAX_EVENTS];
static void set_socket_non_blocking(int sfd);
static char buf[512];
static void send_response(int sfd)
{
int cfd = open("index.html", O_RDONLY, 0777);
if (cfd < 0)
perror("open:");
struct stat stats_buf;
int byte_to_send = fstat(cfd, &stats_buf);
if (byte_to_send < 0)
perror("fstats");
char good_response[1024] = {"HTTP/1.1 200 OK\r\n\r\n"};
send(sfd, good_response, strlen(good_response), 0);
int ret = sendfile(sfd, cfd, NULL, stats_buf.st_size);
if (ret < 0)
perror("send file/response\r\n");
close(sfd);
}
static void handle_client(int cfd)
{
int count = read(cfd, buf, 512);
if (count < 0)
perror("Nothing to read");
struct epoll_event event = {.data.fd = cfd, .events = EPOLLOUT | EPOLLET};
if (epoll_ctl(efd, EPOLL_CTL_MOD, cfd, &event) < 0)
perror("epoll_ctl");
}
static void accept_connection()
{
struct sockaddr addr;
socklen_t addr_len;
int conn_fd = accept(lfd, &addr, &addr_len);
if (conn_fd < 0)
perror("accept connection");
set_socket_non_blocking(conn_fd);
struct epoll_event event = {.data.fd = conn_fd,
.events = EPOLLIN | EPOLLET};
if (epoll_ctl(efd, EPOLL_CTL_ADD, conn_fd, &event) < 0) {
close(conn_fd);
perror("epoll_ctl");
}
}
void serve()
{
memset(&events, 0, MAX_EVENTS * sizeof(struct epoll_event));
int evt_list = epoll_wait(efd, events, MAX_EVENTS, -1);
if (evt_list < 0) {
fprintf(stdin, "EPOLL WAIT: efd %d %s\n", evt_list, strerror(errno));
abort();
}
for (int i = 0; i < evt_list; i++) {
if (events[i].events & (EPOLLERR | EPOLLHUP | EPOLLRDHUP)) {
printf("event [%d]: errno %d\n", i, events[i].events);
close(events[i].data.fd);
perror("closing socket");
} else {
if (events[i].data.fd == lfd)
ACT1;
else if (events[i].events & EPOLLIN)
ACT2;
else
ACT3;
}
}
}
static void set_socket_non_blocking(int sfd)
{
int flags = fcntl(sfd, F_GETFL);
if (flags < 0)
perror("fcntl");
flags |= O_NONBLOCK;
if (fcntl(sfd, F_SETFL, flags) < 0)
perror("fcntl");
}
static int create_socket_listener(char *port)
{
struct addrinfo hints, *result, *r_ptr;
memset(&hints, 0, sizeof(struct addrinfo));
hints.ai_family = AF_UNSPEC;
hints.ai_socktype = SOCK_STREAM;
hints.ai_protocol = 0;
hints.ai_flags = AI_PASSIVE;
int s = getaddrinfo(NULL, port, &hints, &result);
if (s != 0) {
fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(s));
exit(EXIT_FAILURE);
}
int sfd;
for (r_ptr = result; r_ptr != NULL; r_ptr = r_ptr->ai_next) {
sfd = socket(r_ptr->ai_family, r_ptr->ai_socktype, r_ptr->ai_protocol);
if (sfd < 0)
continue;
s = setsockopt(sfd, SOL_SOCKET, SO_REUSEADDR, &s, sizeof(int));
if (s < 0) {
perror("setsockopt");
exit(EXIT_FAILURE);
}
if (bind(sfd, r_ptr->ai_addr, r_ptr->ai_addrlen) == 0)
break;
close(sfd);
}
if (!r_ptr) {
perror("Could not bind\n");
freeaddrinfo(result);
exit(EXIT_FAILURE);
}
freeaddrinfo(result);
return sfd;
}
int main()
{
lfd = create_socket_listener(PORT);
set_socket_non_blocking(lfd);
if (listen(lfd, SOMAXCONN) < 0) {
perror("listen");
exit(EXIT_FAILURE);
}
if ((efd = epoll_create(NUM)) < 0) {
close(lfd);
perror("epoll_create");
}
struct epoll_event event = {.data.fd = lfd, .events = EPOLLIN | EPOLLET};
if (epoll_ctl(efd, EPOLL_CTL_ADD, lfd, &event) < 0) {
close(lfd);
perror("epoll_ctl add");
exit(EXIT_FAILURE);
}
for (;;)
serve();
return 0;
}
請補完程式碼。
作答區
ACT1 = ?
(a) send_response(events[i].data.fd)(b) accept_connection()(c) handle_client(events[i].data.fd)
ACT2 = ?
(a) send_response(events[i].data.fd)(b) accept_connection()(c) handle_client(events[i].data.fd)
ACT3 = ?
(a) send_response(events[i].data.fd)(b) accept_connection()(c) handle_client(events[i].data.fd)
NUM = ?
HackMD
