2
\$\begingroup\$

I have written a program to evaluate a postfix expression using a stack. I had my stack implementation using a linked list reviewed here, so I am only including the header file here.

I have taken the postfix expression in form of a string where the operators and operands are delimited by spaces and have used a sentinel at the end to mark the end of the expression.

stack.h

#ifndef STACK_H
#define STACK_H

#include <stdbool.h>

typedef int StackElement;

typedef struct stack_CDT *Stack;

Stack stack_init();

void stack_destroy(Stack s);

bool stack_is_empty(Stack s);

void stack_push(Stack s, StackElement elem);

StackElement stack_pop(Stack s);

#endif

eval_postfix.h

#ifndef EVAL_POSTFIX_H
#define EVAL_POSTFIX_H

// space is the delimiter between the different tokens

extern const char *sentinel;

int eval_postfix(char *exp);

#endif

eval_postfix.c

#include "eval_postfix.h"
#include "stack.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_TOKEN_LEN 25

const char *sentinel = "$";

static char *get_token(char *token, char *exp, int idx)
{
    sscanf(exp + idx, "%s", token);
    return token;
}

static bool is_operator(char *token)
{
    return (strcmp(token, "/") == 0 || strcmp(token, "*") == 0 ||
            strcmp(token, "%") == 0 || strcmp(token, "+") == 0 ||
            strcmp(token, "-") == 0);
}

static int eval(int a, int b, char *op)
{
    if (strcmp(op, "/") == 0)
        return a / b;
    if (strcmp(op, "*") == 0)
        return a * b;
    if (strcmp(op, "%") == 0)
        return a % b;
    if (strcmp(op, "+") == 0)
        return a + b;
    if (strcmp(op, "-") == 0)
        return a - b;

    return 0;
}

int eval_postfix(char *exp)
{
    Stack s = stack_init();
    char token[MAX_TOKEN_LEN + 1];
    int i = 0;
    while (strcmp(get_token(token, exp, i), sentinel) != 0) {
        if (is_operator(token)) {
            int operand1 = stack_pop(s);
            int operand2 = stack_pop(s);
            stack_push(s, eval(operand2, operand1, token));
        } else {
            stack_push(s, (int)strtol(token, NULL, 0));
        }

        i += strlen(token) + 1; // one extra for the space
    }

    int res = stack_pop(s);
    stack_destroy(s);
    return res;
}

test.c

#include "eval_postfix.h"
#include <stdio.h>
#include <string.h>

#define MAX_EXPRESSION_LEN 100

int main()
{
    printf("Enter postfix expression(no more than %d characters): ",
            MAX_EXPRESSION_LEN);
    char exp[MAX_EXPRESSION_LEN + 3];
    fgets(exp, sizeof exp, stdin);
    char *pos;
    if ((pos = strchr(exp, '\n')) != NULL)
        *pos = '\0';
    strcat(strcat(exp, " "), sentinel);

    printf("Result = %d\n", eval_postfix(exp));
    return 0;
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Optimize strcmp chains

Some of your functions use strcmp() repeatedly. You could make those functions faster by eliminating the multiple calls to strcmp() and using switch statements instead. This function:

static bool is_operator(char *token)
{
    return (strcmp(token, "/") == 0 || strcmp(token, "*") == 0 ||
            strcmp(token, "%") == 0 || strcmp(token, "+") == 0 ||
            strcmp(token, "-") == 0);
}

would become:

static bool is_operator(const char *token)
{
    if (token[1] != '\0')
        return false;

    switch (token[0]) {
        case '/':
        case '*':
        case '%':
        case '+':
        case '-':
            return true;
        default:
            return false;
    }
}

This function:

static int eval(int a, int b, char *op)
{
    if (strcmp(op, "/") == 0)
        return a / b;
    if (strcmp(op, "*") == 0)
        return a * b;
    if (strcmp(op, "%") == 0)
        return a % b;
    if (strcmp(op, "+") == 0)
        return a + b;
    if (strcmp(op, "-") == 0)
        return a - b;

    return 0;
}

could become:

static int eval(int a, int b, const char *op)
{
    switch (*op) {
        case '/':
            return a / b;
        case '*':
            return a * b;
        case '%':
            return a % b;
        case '+':
            return a + b;
        case '-':
            return a - b;
        default:
            return 0;
    }
}

Notice I also added a const to your string arguments because they aren't modified by your functions.

Confusing variable names

This code confused me a little:

        int operand1 = stack_pop(s);
        int operand2 = stack_pop(s);
        stack_push(s, eval(operand2, operand1, token));

Here, operand1 is actually the second operand, and operand2 is actually the first operand, as you can see from the call to eval(). I would have rewritten it like this, because otherwise it would get confusing if someone were stepping through it with a debugger and examining variable values:

        int operand2 = stack_pop(s);
        int operand1 = stack_pop(s);
        stack_push(s, eval(operand1, operand2, token));
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.