Arithmetic evaluation: Difference between revisions

Content added Content deleted
(→‎{{header|Pascal}}: Link to separate example page)
(→‎{{header|C}}: Link to separate example page)
Line 155: Line 155:
euler's number is about: 2.71828182845899446428546958
euler's number is about: 2.71828182845899446428546958
=={{header|C}}==
=={{header|C}}==
See [[Arithmetic Evaluator/C]].
'''Compiler:''' [[gcc]] (version 4.3.2 20081105 (Red Hat 4.3.2-7))


This is a LL(1) recursive descent parser. Only performs integer division. There is a function for every non-terminal in the grammar, save add_op and mult_op, which were lumped into term_tail and factor_tail respectively.

<lang c>#include "stdlib.h"
#include "stdio.h"
#include "ctype.h"

unsigned int G_STRING_ITERATOR = 0;

/*
* expr := term term_tail
* term_tail := add_op term term_tail | e
* term := factor factor_tail
* factor_tail := mult_op factor factor_tail | e
* factor := ( expr ) | number
* add_op := + | -
* mult_op := * | /
*/

typedef union {
int terminal;
struct expression* expr[2];
} Data;

typedef struct expression {
char op;
Data data;
} Expr;

void parse_error(const char* string) {
unsigned int i;
fprintf(stderr, "Unexpected symbol '%c' at position %u.\n\n", string[G_STRING_ITERATOR], G_STRING_ITERATOR);
fprintf(stderr, "String: '%s'\n", string);
fprintf(stderr, "Problem: ");
for(i = 0; i < G_STRING_ITERATOR; ++i) {
fprintf(stderr, " ");
}
fprintf(stderr, "^\n");
exit(1);
}

char consume_char(const char* string, char c) {
if(string[G_STRING_ITERATOR] != c) {
parse_error(string);
}
++G_STRING_ITERATOR;
return c;
}

int consume_int(const char* string) {
int i;

if(!isdigit(string[G_STRING_ITERATOR])) {
parse_error(string);
}

i = atoi(string + G_STRING_ITERATOR);
while(isdigit(string[G_STRING_ITERATOR])) {
++G_STRING_ITERATOR;
}
return i;
}

Expr* expression(const char* string);

Expr* factor(const char* string, Expr* expr) {
if(string[G_STRING_ITERATOR] == '(') {
expr->op = consume_char(string, '(');
expr->data.expr[0] = expression(string);
consume_char(string, ')');
} else if(isdigit(string[G_STRING_ITERATOR])) {
expr->op = 'd';
expr->data.terminal = consume_int(string);
}
return expr;
}

Expr* factor_tail(const char* string, Expr* expr) {
Expr* new_expr;

switch(string[G_STRING_ITERATOR]) {
case '*':
case '/':
if(NULL == (new_expr = (Expr*)malloc(sizeof(Expr)))) {
exit(1);
}
if(NULL == (new_expr->data.expr[1] = (Expr*)malloc(sizeof(Expr)))) {
exit(1);
}
new_expr->op = consume_char(string, string[G_STRING_ITERATOR]);
new_expr->data.expr[0] = expr;

new_expr->data.expr[1] = factor(string, new_expr->data.expr[1]);
new_expr = factor_tail(string, new_expr);
return new_expr;
case '+':
case '-':
case ')':
case 0:
return expr;
default:
parse_error(string);
}
}

Expr* term(const char* string, Expr* expr) {
if(string[G_STRING_ITERATOR] == '(' || isdigit(string[G_STRING_ITERATOR])) {
expr = factor(string, expr);
expr = factor_tail(string, expr);
return expr;
} else {
parse_error(string);
}
}

Expr* term_tail(const char* string, Expr* expr) {
Expr* new_expr;

switch(string[G_STRING_ITERATOR]) {
case '+':
case '-':
if(NULL == (new_expr = (Expr*)malloc(sizeof(Expr)))) {
exit(1);
}
if(NULL == (new_expr->data.expr[1] = (Expr*)malloc(sizeof(Expr)))) {
exit(1);
}
new_expr->op = consume_char(string, string[G_STRING_ITERATOR]);
new_expr->data.expr[0] = expr;

new_expr->data.expr[1] = term(string, new_expr->data.expr[1]);
new_expr = term_tail(string, new_expr);
return new_expr;
case ')':
case 0:
return expr;
default:
parse_error(string);
}
}

Expr* expression(const char* string) {
Expr* expr;

if(string[G_STRING_ITERATOR] == '(' || isdigit(string[G_STRING_ITERATOR])) {
if(NULL == (expr = (Expr*)malloc(sizeof(Expr)))) {
exit(1);
}

expr = term(string, expr);
expr = term_tail(string, expr);
return expr;
} else {
parse_error(string);
}
}

int evaluate(Expr* expr) {
int ret;

switch(expr->op) {
case '(':
ret = evaluate(expr->data.expr[0]);
free(expr->data.expr[0]);
break;
case '*':
ret =
evaluate(expr->data.expr[0])
*
evaluate(expr->data.expr[1])
;
free(expr->data.expr[0]);
free(expr->data.expr[1]);
break;
case '/':
ret =
evaluate(expr->data.expr[0])
/
evaluate(expr->data.expr[1])
;
free(expr->data.expr[0]);
free(expr->data.expr[1]);
break;
case '+':
ret =
evaluate(expr->data.expr[0])
+
evaluate(expr->data.expr[1])
;
free(expr->data.expr[0]);
free(expr->data.expr[1]);
break;
case '-':
ret =
evaluate(expr->data.expr[0])
-
evaluate(expr->data.expr[1])
;
free(expr->data.expr[0]);
free(expr->data.expr[1]);
break;
case 'd':
ret = expr->data.terminal;
break;
default:
exit(1);
}
return ret;
}

int main(int argc, char** argv) {
Expr* expr = NULL;

if(argc > 1) {
expr = expression(argv[1]);
printf("%d\n", evaluate(expr));
free(expr);
}
return 0;
}
</lang>
=={{header|C++}}==
=={{header|C++}}==
{{Works with|g++|4.1.2 20061115 (prerelease) (SUSE Linux)}}
{{Works with|g++|4.1.2 20061115 (prerelease) (SUSE Linux)}}