多项式

```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;
}
```

epee_no_front's Notes

导航

最近发表

友情链接