Spaces:
Sleeping
Sleeping
File size: 4,216 Bytes
9f135d5 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 | // Expression evaluator using Shunting Yard algorithm and stack-based evaluation
// Parses and evaluates infix mathematical expressions with operators and parentheses
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#define MAX_EXPR_LEN 256
#define NUM_TESTS 50000
typedef struct {
double data[MAX_EXPR_LEN];
int top;
} DoubleStack;
typedef struct {
char data[MAX_EXPR_LEN];
int top;
} CharStack;
void double_push(DoubleStack *s, double val) {
if (s->top < MAX_EXPR_LEN) s->data[s->top++] = val;
}
double double_pop(DoubleStack *s) {
return s->top > 0 ? s->data[--s->top] : 0;
}
void char_push(CharStack *s, char val) {
if (s->top < MAX_EXPR_LEN) s->data[s->top++] = val;
}
char char_pop(CharStack *s) {
return s->top > 0 ? s->data[--s->top] : '\0';
}
char char_peek(CharStack *s) {
return s->top > 0 ? s->data[s->top - 1] : '\0';
}
int precedence(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
int is_operator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
double apply_op(double a, double b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return b != 0 ? a / b : 0;
}
return 0;
}
double evaluate_expression(const char *expr) {
DoubleStack values = {.top = 0};
CharStack ops = {.top = 0};
int i = 0;
while (expr[i]) {
if (isspace(expr[i])) {
i++;
continue;
}
if (isdigit(expr[i]) || expr[i] == '.') {
double val = 0;
int decimal = 0;
double divisor = 1;
while (isdigit(expr[i]) || expr[i] == '.') {
if (expr[i] == '.') {
decimal = 1;
} else if (decimal) {
divisor *= 10;
val += (expr[i] - '0') / divisor;
} else {
val = val * 10 + (expr[i] - '0');
}
i++;
}
double_push(&values, val);
} else if (expr[i] == '(') {
char_push(&ops, expr[i]);
i++;
} else if (expr[i] == ')') {
while (ops.top > 0 && char_peek(&ops) != '(') {
char op = char_pop(&ops);
double b = double_pop(&values);
double a = double_pop(&values);
double_push(&values, apply_op(a, b, op));
}
if (ops.top > 0) char_pop(&ops); // Pop '('
i++;
} else if (is_operator(expr[i])) {
while (ops.top > 0 && precedence(char_peek(&ops)) >= precedence(expr[i])) {
char op = char_pop(&ops);
double b = double_pop(&values);
double a = double_pop(&values);
double_push(&values, apply_op(a, b, op));
}
char_push(&ops, expr[i]);
i++;
} else {
i++;
}
}
while (ops.top > 0) {
char op = char_pop(&ops);
double b = double_pop(&values);
double a = double_pop(&values);
double_push(&values, apply_op(a, b, op));
}
return values.top > 0 ? values.data[0] : 0;
}
int main() {
const char *expressions[] = {
"3 + 5 * 2",
"(3 + 5) * 2",
"10 / 2 + 3",
"2 * (3 + 4) - 5",
"100 / (2 + 3) * 4"
};
int num_expr = 5;
clock_t start = clock();
double sum = 0.0;
for (int iter = 0; iter < NUM_TESTS; iter++) {
const char *expr = expressions[iter % num_expr];
sum += evaluate_expression(expr);
}
clock_t end = clock();
double time_spent = (double)(end - start) / CLOCKS_PER_SEC;
printf("Expression evaluator: %d evaluations, %.6f seconds\n",
NUM_TESTS, time_spent);
printf("Sum of results: %.2f\n", sum);
return 0;
}
|