epee_no_front's Notes
Happy learning! Happy Coding!
Toggle navigation
epee_no_front's Notes
主页
codeforces
人工智能
JAVA
python
Latex&Markdown
计算机系统
关于我
归档
标签
多项式
无
2020-09-15 09:59:22
405
0
0
admin
```cpp #include <sys/types.h> #include <regex.h> #include <stdbool.h> #include <stdio.h> #include <string.h> #include <assert.h> #define Log printf typedef unsigned int uint32_t; enum { NOTYPE = 256, HEX, DEC, REG, LP, RP, NEG, DEREF, NOT, PROD, DIV, PLUS, SUB, EQ, NEQ, AND, OR /* TODO: Add more token types */ }; static struct rule { char *regex; int token_type; } rules[] = { /* TODO: Add more rules. * Pay attention to the precedence level of different rules. */ {" +", NOTYPE}, // spaces {"0(x|X)[0-9a-fA-F]+", HEX}, // hex {"[0-9]+", DEC}, // dec {"\\$[a-zA-Z]+", REG}, // register {"\\(", LP}, // left parenthese {"\\)", RP}, // right parenthese {"\\*", PROD}, // prod {"/", DIV}, // div {"\\+", PLUS}, // plus {"\\-", SUB}, // sub {"==", EQ}, // equal {"!=", NEQ}, // not equal {"\\!", NOT}, // not {"&&", AND}, //and {"\\|\\|", OR} //or }; #define NR_REGEX (sizeof(rules) / sizeof(rules[0]) ) static regex_t re[NR_REGEX]; /* Rules are used for many times. * Therefore we compile them only once before any usage. */ void init_regex() { int i; char error_msg[128]; int ret; for(i = 0; i < NR_REGEX; i ++) { ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED); if(ret != 0) { regerror(ret, &re[i], error_msg, 128); // Assert(ret == 0, "regex compilation failed: %s\n%s", error_msg, rules[i].regex); } } } typedef struct token { int type; char str[32]; } Token; Token tokens[32]; int nr_token; int priority[32]; static bool make_token(char *e) { init_regex(); int position = 0; int i; regmatch_t pmatch; printf("%d\n", position); nr_token = 0; while(e[position] != '\0') { printf("%d\n", position); /* Try all rules one by one. */ for(i = 0; i < NR_REGEX; i ++) { if(regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) { char *substr_start = e + position; int substr_len = pmatch.rm_eo; Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s\n", i, rules[i].regex, position, substr_len, substr_len, substr_start); position += substr_len; /* TODO: Now a new token is recognized with rules[i]. Add codes * to record the token in the array `tokens'. For certain types * of tokens, some extra actions should be performed. */ if(rules[i].token_type == NOTYPE) break; tokens[nr_token].type = rules[i].token_type; strncpy(tokens[nr_token].str, substr_start, substr_len); tokens[nr_token].str[substr_len] = '\0'; int last = nr_token - 1; switch (tokens[nr_token].type) { case SUB: if(nr_token == 0 || (tokens[last].type != RP && tokens[last].type != DEC && tokens[last].type != REG && tokens[last].type != HEX)){ Log("%d %d\n", tokens[last].type, REG); tokens[nr_token].type = NEG; } break; case PROD: if(nr_token == 0 || (tokens[last].type != RP && tokens[last].type != DEC && tokens[last].type != REG && tokens[last].type != HEX)){ Log("%d %d\n", tokens[last].type, REG); tokens[nr_token].type = DEREF; } break; default: break; } ++nr_token; break; } } if(i == NR_REGEX) { printf("no match at position %d\n%s\n%*.s^\n", position, e, position, ""); return false; } } return true; } int get_register_value(char *e, bool *ok){ // TODO } bool check_parentheses(int l, int r){ if(tokens[l].type != LP || tokens[r].type != RP) return false; bool ok = true; int cnt = 0; for(int cur = l + 1; cur <= r - 1; cur++) { if(tokens[cur].type == LP) ++cnt; else if(tokens[cur].type == RP) --cnt; if(cnt < 0) { ok = false; break; } } if(cnt != 0) ok = false; return true; } int get_dominant_operator_id(int l, int r){ // TODO int ans = -1, cur_max_priority = -1, cur_left_parenthese = 0, i; for(i = l; i <= r; i++){ if(priority[i] == 0) continue; if(tokens[i].type == LP) cur_left_parenthese++; else if(tokens[i].type == RP) cur_left_parenthese--; if(cur_left_parenthese > 0) continue; if(cur_max_priority <= priority[i]){ cur_max_priority = priority[i]; ans = i; } } if(ans != -1 && priority[ans] == 2){ cur_max_priority = -1; cur_left_parenthese = 0; for(i = l; i <= r; i++){ if(priority[i] == 0) continue; if(tokens[i].type == LP) cur_left_parenthese++; else if(tokens[i].type == RP) cur_left_parenthese--; if(cur_left_parenthese > 0) continue; if(cur_max_priority < priority[i]){ cur_max_priority = priority[i]; ans = i; } } } return ans; } struct type_to_priority{ int type, priority; } type_to_priority_table[] = { {DEC, 0}, {HEX, 0}, {REG, 0}, {LP, 1}, {RP, 1}, {NEG, 2}, {DEREF, 2}, {NOT, 2}, // unary operator, right union {PROD, 3}, {DIV, 3}, {PLUS, 4}, {SUB, 4}, {EQ, 5}, {NEQ, 5}, {AND, 6}, {OR, 7} }; #define NR_TYPE_TO_PRIORITY (sizeof(type_to_priority_table) / sizeof(type_to_priority_table[0]) ) void get_tokens_priority(){ int i, j; for(i = 0; i < nr_token; i++){ for(j = 0; j < NR_TYPE_TO_PRIORITY; j++){ if(type_to_priority_table[j].type == tokens[i].type){ priority[i] = type_to_priority_table[j].priority; break; } } } return ; } int eval(int l, int r){ if(l > r){ printf("Bad expression\n"); assert(0); } else if(l == r){ int ans; bool ok; switch (tokens[l].type) { case DEC: sscanf(tokens[l].str, "%d", &ans); return ans; case HEX: sscanf(tokens[l].str, "%x", &ans); return ans; case REG: ok = true; ans = get_register_value(tokens[l].str, &ok); if(ok) return ans; else { printf("register %s not exists\n", tokens[l].str); assert(0); } default: printf("Bad expression\n"); assert(0); } } else if(check_parentheses(l, r) == true){ return eval(l + 1, r - 1); } else { // TODO int dominant_operator_id = get_dominant_operator_id(l, r); printf("dn: %d\n", dominant_operator_id); printf("%d %d\n", l, r); if(dominant_operator_id == -1){ printf("bad expression\n"); assert(0); } else if(priority[dominant_operator_id] == 2){ if(dominant_operator_id != l) { printf("bad expression\n"); assert(0); } else { int num = eval(dominant_operator_id + 1, r); switch (tokens[dominant_operator_id].type) { case NEG: num = -num; break; case NOT: num = !num; break; case DEREF: //TODO break; default: break; } return num; } } else { int num1 = eval(l, dominant_operator_id - 1); int num2 = eval(dominant_operator_id + 1, r); switch (tokens[dominant_operator_id].type) { case PROD: return num1 * num2; case DIV: if(num2 == 0) { printf("diviede by zero\n"); assert(0); } return num1 / num2; case PLUS: return num1 + num2; case SUB: return num1 - num2; case EQ: return num1 == num2 ? 1 : 0; case NEQ: return num1 != num2 ? 1 : 0; case AND: return (int) (num1 && num2); case OR: return (int) (num1 || num2); default: printf("unknown error\n"); assert(0); } } } } uint32_t expr(char *e, bool *success) { if(!make_token(e)) { *success = false; return 0; } int i; printf("nr_token: %d\n", nr_token); for(i = 0; i < nr_token; i++){ printf("%s %d\n", tokens[i].str, tokens[i].type); } /* TODO: Insert codes to evaluate the expression. */ get_tokens_priority(); // panic("please implement me"); return eval(0, nr_token - 1); } int main(){ char s[1000]; // fgets(s, 999, stdin); gets(s); bool ok = true; // printf("%s\n", s); printf("ans: %d\n", expr(s, &ok)); return 0; } ```
上一篇:
NEMU资料
下一篇:
关于nohup
0
赞
405 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
皖ICP备20006612号
皖公网安备 34020302000165号
文档导航
没有帐号? 立即注册