Упражнение 5.10. Напишите программу expr( K&R) - C (СИ)
Формулировка задачи:
Условие: Напишите программу expr, интерпретирующую обратную польскую запись выражения,
задаваемого командной строкой, в которой каждый оператор и операнд представлены отдельным
аргументом. Например,
expr 2 3 4 + *
вычисляется так же, как выражение 2 х (3 + 4).
если ввожу 2 3 + , получается 5
если 2 3 4 + * получается error: unknown command a
5
Подскажите, пожалуйста, где ошибка
#include <stdio.h>
#include <stdlib.h> //for atof()
#include <math.h>
#define MAXOP 100 //max size of operand or operator
#define NUMBER '0' //signal that a number was found
int getop(char[]);
void ungetch(char[]);
void push(double);
double pop(void);
int main(int argc, char *argv[])
{
double op2;
char s[MAXOP];
while(--argc > 0)
{
ungetch(" ");
ungetch(*++argv);
switch(getop(s))
{
case NUMBER:
push(atof(s));
break;
case '+':
push(pop() + pop());
break;
case '*':
push(pop() + pop());
break;
case '-':
op2 = pop();
push(pop() - op2);
break;
case '/':
op2 = pop();
if(op2 != 0.0)
push(pop() / op2);
else
printf("error: zero devisior\n");
break;
default:
printf("error: unknown command %s\n", s);
argc = 1;
break;
}
}
printf("\t%.8g\n", pop());
return 0;
}
#define MAXVAL 100 //maximum depth of val stack
double val[MAXVAL]; //value stack
int sp = 0; //next free stack position
/* push: push f into value stack */
void push(double f)
{
if(sp < MAXVAL)
val[sp++] = f;
else
printf("error: stack full, can`t push %g\n", f);
}
/* pop: pop and return top value from stack */
double pop(void)
{
if(sp > 0)
return val[--sp];
else
{
printf("error: stack empty\n");
return 0.0;
}
}
#include <ctype.h>
int getch(void);
void ungetch(char []);
/* getop: get next character ot numeric operand */
int getop(char s[])
{
int i, c;
while((s[0] = c = getch()) == ' ' || c == '\t')
;
s[1] = '\0';
if(!isdigit(c) && c != '.') // not a nember
return c;
i = 0;
if(isdigit(c)) //collect integer part
while(isdigit(s[++i] = c = getch()))
;
if(c == '.') //collect fraction part
while(isdigit(s[++i] = c = getch()))
;
s[i] = '\0';
return NUMBER;
}
#define BUFSIZE 100
char buf[BUFSIZE]; //buffer for ungetch;
int bufp = 0; //next free position in bud
int getch(void) // get a (possibly pushed-back) character
{
return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(char argv[]) // push character back on input
{
if(bufp >= BUFSIZE)
printf("ungetch: too many characnters\n");
else
buf[bufp++] = *argv;
}Решение задачи: «Упражнение 5.10. Напишите программу expr( K&R)»
textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
enum token_type {
PLUS, MINUS, MULT, DIV, ERR, NUMBER
};
enum token_type get_token_type(const char *, const char **);
double plus(double x, double y);
double minus(double x, double y);
double mult(double x, double y);
double divide(double x, double y);
typedef double (*op)(double, double);
op op_table[] = {
plus, minus, mult, divide
};
struct stack;
struct stack *create_stack(const char **);
void destroy_stack(struct stack *);
bool empty(struct stack *);
double pop(struct stack *, const char **);
void push(struct stack *, double, const char **);
int main(int argc, char *argv[])
{
const char *err = NULL;
int retval;
if(argc < 2) {
err = "No expression given";
goto err;
}
struct stack *stack = create_stack(&err);
if(err) {
goto err;
}
for(int i = 1; argv[i] != NULL; ++i) {
enum token_type token_type = get_token_type(argv[i], &err);
switch(token_type) {
case NUMBER:
push(stack, atof(argv[i]), &err);
if(err) {
goto err_free_stack;
}
break;
case PLUS:
case MINUS:
case MULT:
case DIV:
{
double op2 = pop(stack, &err);
if(err) {
goto err_free_stack;
}
double op1 = pop(stack, &err);
if(err) {
goto err_free_stack;
}
op operator = op_table[token_type];
if(token_type == DIV && fpclassify(op2) == FP_ZERO) {
err = "Division by zero";
goto err_free_stack;
}
push(stack, operator(op1, op2), &err);
if(err) {
goto err_free_stack;
}
break;
}
case ERR:
goto err_free_stack;
break;
}
}
double value = pop(stack, &err);
if(err) {
goto err_free_stack;
}
if(!empty(stack)) {
err = "Extra input";
goto err_free_stack;
}
printf("> %.2f\n", value);
retval = EXIT_SUCCESS;
goto exit;
err_free_stack:
if(stack) {
destroy_stack(stack);
}
err:
if(err) {
fprintf(stderr, "%s\n", err);
}
retval = EXIT_FAILURE;
exit:
exit(retval);
}
struct stack_node
{
double value;
struct stack_node *next;
};
struct stack
{
struct stack_node *top;
};
struct stack *create_stack(const char **err)
{
struct stack *retval = malloc(sizeof *retval);
if(retval) {
retval->top = NULL;
} else if(err) {
*err = "create_stack: can't allocate memory for stack";
}
return retval;
}
void destroy_stack_node(struct stack_node *node)
{
if(node) {
destroy_stack_node(node->next);
free(node);
}
node = NULL;
}
void destroy_stack(struct stack *stack)
{
destroy_stack_node(stack->top);
}
bool empty(struct stack *stack)
{
return stack->top == NULL;
}
double pop(struct stack *stack, const char **err)
{
double retval = 0.0;
if(empty(stack)) {
if(err) {
*err = "pop: stack is empty";
}
} else {
struct stack_node *node = stack->top;
retval = node->value;
stack->top = stack->top->next;
free(node);
node = NULL;
}
return retval;
}
void push(struct stack *stack, double value, const char **err)
{
struct stack_node *node = malloc(sizeof *node);
if(node) {
node->next = stack->top;
node->value = value;
stack->top = node;
} else if(err) {
*err = "push: can't allocate memory for stack node";
}
}
#include <ctype.h>
#include <string.h>
enum token_type get_token_type(const char *lexeme, const char **err)
{
static const char *ops = "+-*/";
enum token_type retval;
bool trailing_space = false;
const char *ch;
enum {
start, operator, integral,
integral_dot, floating,
error
} state = start;
while(*lexeme && state != error) {
switch(state) {
case start:
if(isspace(*lexeme)) {
++lexeme;
} else if((ch = strchr(ops, *lexeme))) {
retval = ch - ops;
state = operator;
++lexeme;
} else if(isdigit(*lexeme)) {
state = integral;
++lexeme;
} else {
if(err) {
*err = "get_token_type: unexpected characters at the beginning of lexeme";
}
state = error;
}
break;
case operator:
if(isspace(*lexeme)) {
trailing_space = true;
} else {
if(err) {
*err = "get_token_type: unexpected characters after operator";
}
state = error;
}
++lexeme;
break;
case integral:
if(isspace(*lexeme)) {
trailing_space = true;
++lexeme;
} else if(trailing_space) {
state = error;
if(err) {
*err = "get_token_type: unexpected trailing characters after integer";
}
} else if(isdigit(*lexeme)) {
++lexeme;
} else if(*lexeme == '.') {
state = integral_dot;
++lexeme;
} else {
if(err) {
*err = "get_token_type: unexpected characters after integral literal";
}
state = error;
}
break;
case integral_dot:
if(isdigit(*lexeme)) {
state = floating;
++lexeme;
} else {
if(err) {
*err = "get_token_type: incomplete floating literal";
}
state = error;
}
break;
case floating:
if(isspace(*lexeme)) {
trailing_space = true;
++lexeme;
} else if(trailing_space) {
if(err) {
*err = "get_token_type: unexpected characters after floating literal";
}
state = error;
} else if(isdigit(*lexeme)) {
++lexeme;
} else {
if(err) {
*err = "get_token_type: unexpected characters after floating literal";
}
}
break;
case error:
break;
}
}
switch(state) {
case operator:
break;
case integral:
case floating:
retval = NUMBER;
break;
case start:
retval = ERR;
if(err) {
*err = "get_token_type: empty lexeme";
}
break;
case integral_dot:
if(err) {
*err = "get_token_type: incomplete floating literal";
}
case error:
retval = ERR;
break;
}
return retval;
}
double plus(double x, double y)
{
return x + y;
}
double minus(double x, double y)
{
return x - y;
}
double mult(double x, double y)
{
return x * y;
}
double divide(double x, double y)
{
return x / y;
}