4
\$\begingroup\$

Just over half way through in K&R, came across an exercise to convert from postfix ("reverse-Polish") notation to infix (standard) notation.

Basically I'm posting here to see if there is anything excessive in my code, or any way to reduce the amount of storage it takes up. It runs extremely fast and doesn't take up much space, but if space can be reduced I believe it always should be.

Also, I have tried to maintain the clearest readability and consistent style throughout my code, but I am new to C, so if there are certain style conventions I am breaking, let me know as well.

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAXLEN 1000    // Maximum string length

int isOperator(int c);
void addPrecedence(char * infixExpr);
void pushExpression(char * infixExpr);
char * popExpression(void);

int main(int argc, char * argv[])
{
    // Only one argument is allowed
    if (argc != 2) {
        printf("Usage: evaluate [expression] from postfix to infix\n");
        return 1;
    }

    int i;
    char * expression = argv[1];
    char left[MAXLEN], right[MAXLEN], expr[MAXLEN];

    for (i = 0; expression[i] != '\0'; i++) {
        if (isalpha(expression[i]) || isdigit(expression[i])) {
            // Copy character into a string so it can be pushed onto the stack
            expr[0] = expression[i], expr[1] = '\0';
            pushExpression(expr);

        } else if (isOperator(expression[i])) {
            strcpy(right, popExpression());
            strcpy(left, popExpression());

            expr[0] = expression[i], expr[1] = '\0';
            strcat(left, expr);
            strcat(left, right);
            addPrecedence(left);
            pushExpression(left);

        } expr[0] = '\0';    // Reset expr character array
    }
    printf("%s\n", popExpression());
    return 0;
}

// Check if the character is a valid operator
int isOperator(int c)
{
    int i;
    char legalOps[] = {'+', '-', '*', '/'};

    for (i = 0; i < 4; i++)
        if (c == legalOps[i])
            return 1;
    return 0;
}

// Wrap the expression in paranthesis to maintain order of precedence
void addPrecedence(char * infixExpr)
{
    int i, needsPrecedence = 0;

    // Check if parens are even needed
    for (i = 0; infixExpr[i] != '\0'; i++) {
        if (infixExpr[i] == '(') {
            break;

        } else if (infixExpr[i] == '+' || infixExpr[i] == '-') {
            needsPrecedence = 1;
            break;
        }
    }
    // If parens are needed, insert them at the beginning and end
    if (needsPrecedence) {
        infixExpr[strlen(infixExpr)] = ')';
        for (i = strlen(infixExpr)-1; i >= 0; i--)
            infixExpr[i+1] = infixExpr[i];
        infixExpr[0] = '(';
    }
}


#define MAXEXPR 100    // Maximum expression stack value

// Create expression stack
char expressionStack[MAXEXPR][MAXLEN];
int currentExpr = 0;

// Push an expression (character array) onto the expression stack
void pushExpression(char * infixExpr)
{
    int i = 0;

    // Copy each character from infixExpr into the expression stack
    while (*infixExpr != '\0')
        expressionStack[currentExpr][i++] = *infixExpr++;

    // Delete any additional data from previous stack value
    expressionStack[currentExpr][i] = '\0';
    ++currentExpr;
}

// Return expression (character array) from top of stack
char * popExpression(void)
{
    // Return NULL if expression stack is empty
    if (currentExpr == 0 || expressionStack[currentExpr-1][0] == '\0') {
        return 0;

    } else {
        // Save expression to be returned, then delete it from the stack
        char * expr = expressionStack[--currentExpr];
        return expr;
    }
}
\$\endgroup\$
4
\$\begingroup\$

Since you are using end-of-line commands, I will assume that you are using at least C99 in this review (it may be a compiler extension to C89 though).

main

There are too many things in your main function. It shouldn't handle the expression parsing, but delegate this task to another function. Also, if you are using C99, you don't need to return 0; at the end of main: the compiler will have your program automagically return 0 when it reaches the end of the function.

isOperator

Whenever it makes sense, try to use boolean values instead of integers. The header <stdbool.h> defines bool, true and false that you can use to make your code clearer. Using booleans instead of integers can help to clarify your intent. For example, here is your function isOperator with booleans instead of integers

bool isOperator(int c)
{
    int i;
    char legalOps[] = {'+', '-', '*', '/'};

    for (i = 0; i < 4; i++)
        if (c == legalOps[i])
            return true;
    return false;
}

By the way, there are many other way to implement this function. Your current function uses a loop and therefore performs in \$ O(n) \$ where n is the number of operators while you could rewrite it to perform in \$ O(1) \$, with a lookup table for example. That said, it shouldn't be a problem since you only have 4 operators.

Variable declarations

You seem to declare your variables at the beginning of blocks. It is not needed anymore with C99, you can declare your variable when you need it. You can also declare a variable in a for loop and therefore write things like this:

for (int i = 0; infixExpr[i] != '\0'; i++) {
    // ...
}
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the suggestions! I'll definitely look to improve isOperator with a lookup table. And yes I am using C99, so I'll make use of the other details you provided. Thanks again! \$\endgroup\$
    – samrap
    May 23 '14 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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