Postfix evaluation using a stack in c

Question

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;
}

Answer 1

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));