/* One-line Input Calculator by CynusW * Goal: understanding more about Pratt's parser. * * Example: 1 + 2 - 3 * 4 / (-5^2) * * Supported operations: * - Addition: 1 + 2 * - Associativity: left-right * - Subtraction: 2 - 3 * - Associativity: left-right * - Multiplication: 4 * 5 * - Associativity: left-right * - Division: 6 / 7 * - Associativity: left-right * - Power: 8 ^ 9 * - Associativity: right-left * - Negation: -10 * - Associativity: right-left * - Grouping: (11 + 12) */ /* ================================================ * Standard Library Headers * ================================================ */ #include #include #include #include #include #include #include /* ================================================ * Macros * ================================================ */ #define MAX_STACK 0x100 #define GROW_CAPACITY(capacity) \ ((capacity) < 16 ? 16 : 2 * (capacity)) #define GROW_ARRAY(array, type, new_capacity) \ (type*)reallocate(array, (new_capacity) * sizeof(type)) /* ================================================ * Enums * ================================================ */ typedef enum token_type { // Single-character tokens TOKEN_LEFT_PAREN, TOKEN_RIGHT_PAREN, TOKEN_PLUS, TOKEN_MINUS, TOKEN_SLASH, TOKEN_STAR, TOKEN_POWER, // Literals TOKEN_NUMBER, TOKEN_ERROR, TOKEN_EOF } token_type_t; typedef enum precedence { PREC_NONE, PREC_TERM, PREC_FACTOR, PREC_UNARY, PREC_POWER, PREC_PRIMARY } precedence_t; /* ================================================ * Data Structures * ================================================ */ typedef double value_t; typedef struct scanner { const char *start; const char *current; } scanner_t; typedef struct token { token_type_t type; const char *start; size_t length; } token_t; typedef struct parser { token_t current; token_t previous; } parser_t; typedef void(*parse_func)(void); typedef struct parse_rule { parse_func prefix; parse_func infix; precedence_t precedence; } parse_rule_t; typedef struct string { size_t size; size_t capacity; char *chars; } string_t; typedef struct value_stack { value_t values[MAX_STACK]; value_t *stackTop; } value_stack_t; /* ================================================ * Global Variables * ================================================ */ bool g_had_error; parser_t g_parser; scanner_t g_scanner; value_stack_t g_stack; /* ================================================ * Forward Declarations * ================================================ */ // INTERPRETER void advance(); void consume(token_type_t type, const char *message); void parse_expression(); parse_rule_t* get_rule(token_type_t type); void parse_precedence(precedence_t precedence); void parse_number(); void parse_unary(); void parse_binary(); void parse_group(); // SCANNER void scanner_init(const char *src); bool scanner_at_end(); bool scanner_match(char expect); char scanner_peek(); char scanner_advance(); void scanner_skip_whitespace(); token_t scanner_make_token(token_type_t type); token_t scanner_error_token(const char *message); token_t scanner_scan_token(); token_t scanner_scan_number(); void scanner_unexpected(char c); // STRING void string_init(string_t *str); void string_free(string_t *str); void string_write(string_t *str, char c); // STACK void vstack_init(value_stack_t *stack); void vstack_push(value_stack_t *stack, value_t value); value_t vstack_pop(value_stack_t *stack); // UTILITIES void error(const char *message); void error_token(token_t token); string_t read_line(); void* reallocate(void *block, size_t size); void print_stack(); // === MAIN === int main(void) { string_t input = read_line(); scanner_init(input.chars); vstack_init(&g_stack); advance(); parse_expression(); consume(TOKEN_EOF, "Expected end of expression."); string_free(&input); if (g_had_error) exit(65); printf("%g\n", vstack_pop(&g_stack)); return 0; } // INTERPRETER void advance() { g_parser.previous = g_parser.current; for (;;) { g_parser.current = scanner_scan_token(); if (g_parser.current.type != TOKEN_ERROR) return; error_token(g_parser.current); } } void consume(token_type_t type, const char *message) { if (g_parser.current.type == type) { advance(); return; } error(message); } void parse_expression() { parse_precedence(PREC_TERM); } static parse_rule_t rules[] = { { parse_group, NULL, PREC_NONE }, // TOKEN_LEFT_PAREN { NULL, NULL, PREC_NONE }, // TOKEN_RIGHT_PAREN { NULL, parse_binary, PREC_TERM }, // TOKEN_PLUS { parse_unary, parse_binary, PREC_TERM }, // TOKEN_MINUS { NULL, parse_binary, PREC_FACTOR }, // TOKEN_SLASH { NULL, parse_binary, PREC_FACTOR }, // TOKEN_STAR { NULL, parse_binary, PREC_POWER }, // TOKEN_POWER { parse_number, NULL, PREC_NONE }, // TOKEN_NUMBER { NULL, NULL, PREC_NONE }, // TOKEN_ERROR { NULL, NULL, PREC_NONE }, // TOKEN_EOF }; parse_rule_t* get_rule(token_type_t type) { return &rules[type]; } void parse_precedence(precedence_t precedence) { advance(); parse_func prefix_func = get_rule(g_parser.previous.type)->prefix; if (prefix_func == NULL) { error("Expected expression."); return; } prefix_func(); #if defined DEBUG_TRACE_STACK print_stack(); #endif while (get_rule(g_parser.current.type)->precedence >= precedence) { advance(); parse_func infix_func = get_rule(g_parser.previous.type)->infix; infix_func(); #if defined DEBUG_TRACE_STACK print_stack(); #endif } } void parse_number() { value_t value = strtod(g_parser.previous.start, NULL); vstack_push(&g_stack, value); } void parse_unary() { token_type_t type = g_parser.previous.type; parse_precedence(PREC_UNARY); switch (type) { case TOKEN_MINUS: vstack_push(&g_stack, -vstack_pop(&g_stack)); break; default: return; } } void parse_binary() { #define BINARY_OP(op) \ do { \ value_t rhs = vstack_pop(&g_stack); \ value_t lhs = vstack_pop(&g_stack); \ vstack_push(&g_stack, lhs op rhs); \ } while (false) token_type_t type = g_parser.previous.type; if (type == TOKEN_POWER) parse_precedence(PREC_POWER); else parse_precedence(get_rule(type)->precedence + 1); switch (type) { case TOKEN_PLUS: BINARY_OP(+); break; case TOKEN_MINUS: BINARY_OP(-); break; case TOKEN_SLASH: BINARY_OP(/); break; case TOKEN_STAR: BINARY_OP(*); break; case TOKEN_POWER: { value_t rhs = vstack_pop(&g_stack); value_t lhs = vstack_pop(&g_stack); vstack_push(&g_stack, pow(lhs, rhs)); break; } // case TOKEN_POWER default: return; } #undef BINARY_OP } void parse_group() { parse_expression(); consume(TOKEN_RIGHT_PAREN, "Expected ')' after expression."); } // SCANNER void scanner_init(const char *src) { g_scanner.start = src; g_scanner.current = src; } bool scanner_at_end() { return *g_scanner.current == '\0'; } bool scanner_match(char expect) { if (scanner_at_end()) return false; if (scanner_peek() != expect) return false; g_scanner.current++; return true; } char scanner_peek() { return *g_scanner.current; } char scanner_advance() { if (scanner_at_end()) return '\0'; g_scanner.current++; return g_scanner.current[-1]; } void scanner_skip_whitespace() { while (!scanner_at_end() && isspace(scanner_peek())) scanner_advance(); } token_t scanner_make_token(token_type_t type) { return (token_t) { type, g_scanner.start, g_scanner.current - g_scanner.start }; } token_t scanner_error_token(const char *message) { return (token_t) { TOKEN_ERROR, message, strlen(message) }; } token_t scanner_scan_token() { scanner_skip_whitespace(); g_scanner.start = g_scanner.current; if (scanner_at_end()) return scanner_make_token(TOKEN_EOF); char c = scanner_advance(); if (isdigit(c)) return scanner_scan_number(); switch (c) { case '(': return scanner_make_token(TOKEN_LEFT_PAREN); case ')': return scanner_make_token(TOKEN_RIGHT_PAREN); case '+': return scanner_make_token(TOKEN_PLUS); case '-': return scanner_make_token(TOKEN_MINUS); case '/': return scanner_make_token(TOKEN_SLASH); case '*': return scanner_make_token(TOKEN_STAR); case '^': return scanner_make_token(TOKEN_POWER); } return scanner_error_token("Unexpected character."); } token_t scanner_scan_number() { while (!scanner_at_end() && isdigit(scanner_peek())) scanner_advance(); if (scanner_match('.')) { while (!scanner_at_end() && isdigit(scanner_peek())) scanner_advance(); } return scanner_make_token(TOKEN_NUMBER); } // STRING void string_init(string_t *str) { str->size = 0; str->capacity = 0; str->chars = NULL; } void string_free(string_t *str) { free(str->chars); string_init(str); } void string_write(string_t *str, char c) { if (str->capacity < str->size+1) { str->capacity = GROW_CAPACITY(str->capacity); str->chars = GROW_ARRAY( str->chars, char, str->capacity+1 ); } str->chars[str->size] = c; str->size++; str->chars[str->size] = '\0'; } // STACK void vstack_init(value_stack_t *stack) { stack->stackTop = stack->values; } void vstack_push(value_stack_t *stack, value_t value) { if (stack->stackTop >= (stack->values + MAX_STACK)) { error("STACK OVERFLOW"); return; } *stack->stackTop = value; stack->stackTop++; } value_t vstack_pop(value_stack_t *stack) { if (stack->stackTop <= stack->values) return 0; return *--stack->stackTop; } // UTILITIES void error(const char *message) { g_had_error = true; fprintf(stderr, "%s\n", message); } void error_token(token_t token) { g_had_error = true; fprintf(stderr, "%.*s\n", (int)token.length, token.start); } string_t read_line() { string_t str; string_init(&str); // Needed for SoloLearn to detect input. scanf(" "); int c; while ((c = fgetc(stdin)) != '\n' && c != EOF) { string_write(&str, (char)c); } return str; } void* reallocate(void *block, size_t size) { if (size == 0) { free(block); return NULL; } return realloc(block, size); } void print_stack() { printf(" "); for (value_t *slot = g_stack.values; slot < g_stack.stackTop; slot++) { printf("[%g]", *slot); } printf("\n"); }