diff options
Diffstat (limited to 'lab04/expression.h')
| -rw-r--r-- | lab04/expression.h | 319 |
1 files changed, 319 insertions, 0 deletions
diff --git a/lab04/expression.h b/lab04/expression.h new file mode 100644 index 0000000..f0e2847 --- /dev/null +++ b/lab04/expression.h @@ -0,0 +1,319 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +#ifndef EXPRESSION_H +#define EXPRESSION_H + +#include <ctype.h> +#include <errno.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdlib.h> +#include <string.h> + +#include "stack.h" + +#define EXPRESSION_NAME_MAX 64 + +enum expression_error_code { + EXPRESSION_OK, + EXPRESSION_SYNTAX_ERROR, + EXPRESSION_PAREN_ERROR, + EXPRESSION_UNKNOWN_VARIABLE, + EXPRESSION_UNSET_VARIABLE, + EXPRESSION_DIVISION_BY_ZERO, +}; + +struct expression_error { + enum expression_error_code code; + size_t position; +}; + +struct expression_variable { + char name[EXPRESSION_NAME_MAX]; + double value; + bool assigned; +}; + +struct expression_context { + struct vec variables; +}; + +static inline void expression_init(struct expression_context *ctx) +{ + vec_init(&ctx->variables, struct expression_variable); +} + +static inline void expression_destroy(struct expression_context *ctx) +{ + vec_destroy(&ctx->variables); +} + +static inline void expression_error(struct expression_error *error, + enum expression_error_code code, + size_t position) +{ + if (error) { + error->code = code; + error->position = position; + } +} + +static inline bool expression_name_start(unsigned char c) +{ + return isalpha(c) || c == '_'; +} + +static inline bool expression_name_char(unsigned char c) +{ + return isalnum(c) || c == '_'; +} + +static inline struct expression_variable * +expression_variable(struct expression_context *ctx, const char *name) +{ + for (size_t i = 0; i < ctx->variables.size; ++i) { + struct expression_variable *v = vec_at(&ctx->variables, i); + if (strcmp(v->name, name) == 0) { + return v; + } + } + return NULL; +} + +static inline bool expression_set_variable(struct expression_context *ctx, + const char *name, + double value) +{ + if (!expression_name_start((unsigned char)name[0]) || + strlen(name) >= EXPRESSION_NAME_MAX) return false; + for (const unsigned char *p = (const unsigned char *)name + 1; *p; ++p) { + if (!expression_name_char(*p)) { + return false; + } + } + struct expression_variable *v = expression_variable(ctx, name); + if (!v) { + struct expression_variable item = { .value = value, .assigned = true }; + strcpy(item.name, name); + if (!vec_push_back(&ctx->variables, &item)) { + return false; + } + } else { + v->value = value; + v->assigned = true; + } + return true; +} + +static inline bool expression_collect_variables(struct expression_context *ctx, + const char *text, + struct expression_error *error) +{ + vec_clear(&ctx->variables); + for (size_t i = 0; text[i];) { + unsigned char c = (unsigned char)text[i]; + if (isspace(c)) { + ++i; + } else if (expression_name_start(c)) { + size_t start = i++; + while (expression_name_char((unsigned char)text[i])) { + ++i; + } + size_t length = i - start; + if (length >= EXPRESSION_NAME_MAX) { + expression_error(error, EXPRESSION_SYNTAX_ERROR, start); + return false; + } + char name[EXPRESSION_NAME_MAX]; + memcpy(name, text + start, length); + name[length] = '\0'; + if (!expression_variable(ctx, name)) { + struct expression_variable item = { .assigned = false }; + strcpy(item.name, name); + if (!vec_push_back(&ctx->variables, &item)) { + expression_error(error, EXPRESSION_SYNTAX_ERROR, start); + return false; + } + } + } else if (isdigit(c) || c == '.' || c == '+' || c == '-' || + c == '*' || c == '/' || c == '(' || c == ')') { + ++i; + } else { + expression_error(error, EXPRESSION_SYNTAX_ERROR, i); + return false; + } + } + expression_error(error, EXPRESSION_OK, 0); + return true; +} + +/** @brief An operator and its byte offset in the expression. */ +struct expression_operator { + char symbol; + size_t position; +}; + +/** @brief Returns precedence; `p` and `n` denote unary plus and minus. */ +static inline int expression_precedence(char symbol) +{ + switch (symbol) { + case 'p': case 'n': return 3; + case '*': case '/': return 2; + case '+': case '-': return 1; + default: return 0; + } +} + +/** @brief Applies the top operator to the value stack. */ +static inline bool expression_apply(stack *values, stack *operators, + struct expression_error *error) +{ + struct expression_operator op = *stack_top_as(operators, struct expression_operator); + stack_pop(operators); + bool unary = op.symbol == 'p' || op.symbol == 'n'; + if (stack_size(values) < (unary ? 1u : 2u)) { + expression_error(error, EXPRESSION_SYNTAX_ERROR, op.position); + return false; + } + if (unary) { + if (op.symbol == 'n') *stack_top_as(values, double) *= -1; + return true; + } + double rhs = *stack_top_as(values, double); + stack_pop(values); + double *lhs = stack_top_as(values, double); + switch (op.symbol) { + case '+': *lhs += rhs; break; + case '-': *lhs -= rhs; break; + case '*': *lhs *= rhs; break; + case '/': + if (rhs == 0.0) { + expression_error(error, EXPRESSION_DIVISION_BY_ZERO, op.position); + return false; + } + *lhs /= rhs; + break; + } + return true; +} + +/** + * @brief Evaluates an expression using value and operator stacks. + * @param ctx The variable table used for name lookup. + * @param text The null-terminated expression. + * @param result Receives the value on success; unchanged on failure. + * @param error Receives the error code and byte offset, or may be null. + * @return `true` on success; otherwise `false`. + * @pre `ctx` is initialized; `text` and `result` are valid pointers. + */ +static inline bool expression_eval(const struct expression_context *ctx, + const char *text, + double *result, + struct expression_error *error) +{ + STACK(values, double); + STACK(operators, struct expression_operator); + bool expect_operand = true; + bool success = false; + size_t position = 0; + + while (text[position]) { + unsigned char c = (unsigned char)text[position]; + if (isspace(c)) { + ++position; + continue; + } + if (isdigit(c) || c == '.' || expression_name_start(c)) { + if (!expect_operand) goto syntax_error; + double value; + if (expression_name_start(c)) { + size_t start = position++; + while (expression_name_char((unsigned char)text[position])) ++position; + size_t length = position - start; + if (length >= EXPRESSION_NAME_MAX) { + position = start; + goto syntax_error; + } + const struct expression_variable *variable = NULL; + for (size_t i = 0; i < ctx->variables.size; ++i) { + const struct expression_variable *v = vec_at_const(&ctx->variables, i); + if (strlen(v->name) == length && + strncmp(v->name, text + start, length) == 0) { + variable = v; + break; + } + } + if (!variable || !variable->assigned) { + expression_error(error, variable ? EXPRESSION_UNSET_VARIABLE + : EXPRESSION_UNKNOWN_VARIABLE, start); + goto done; + } + value = variable->value; + } else { + char *end; + errno = 0; + value = strtod(text + position, &end); + if (end == text + position || errno == ERANGE) goto syntax_error; + position = (size_t)(end - text); + } + if (!stack_push(&values, &value)) goto syntax_error; + expect_operand = false; + continue; + } + struct expression_operator op = { .symbol = (char)c, .position = position }; + if (c == '(') { + if (!expect_operand) goto syntax_error; + } else if (c == ')') { + if (expect_operand) goto syntax_error; + while (!stack_empty(&operators) && + stack_top_as(&operators, struct expression_operator)->symbol != '(') { + if (!expression_apply(&values, &operators, error)) goto done; + } + if (stack_empty(&operators)) goto paren_error; + stack_pop(&operators); + ++position; + continue; + } else if (c == '+' || c == '-' || c == '*' || c == '/') { + if (expect_operand) { + if (c != '+' && c != '-') goto syntax_error; + op.symbol = c == '+' ? 'p' : 'n'; + } else { + while (!stack_empty(&operators) && + expression_precedence(stack_top_as(&operators, + struct expression_operator)->symbol) >= expression_precedence(op.symbol)) { + if (!expression_apply(&values, &operators, error)) goto done; + } + } + } else { + goto syntax_error; + } + if (!stack_push(&operators, &op)) goto syntax_error; + expect_operand = true; + ++position; + } + if (expect_operand) goto syntax_error; + while (!stack_empty(&operators)) { + struct expression_operator op = *stack_top_as(&operators, struct expression_operator); + if (op.symbol == '(') { + position = op.position; + goto paren_error; + } + if (!expression_apply(&values, &operators, error)) goto done; + } + if (stack_size(&values) != 1) goto syntax_error; + *result = *stack_top_as(&values, double); + expression_error(error, EXPRESSION_OK, 0); + success = true; + goto done; + +syntax_error: + expression_error(error, EXPRESSION_SYNTAX_ERROR, position); + goto done; +paren_error: + expression_error(error, EXPRESSION_PAREN_ERROR, position); +done: + stack_destroy(&values); + stack_destroy(&operators); + return success; +} + +#endif /* EXPRESSION_H */ |