postfix.c

Jonas Altrock ew20b126@technikum-wien.at

To overview.

The whole source file postfix.c.

/* compile with `clang -std=c99 -Wall -o postfix postfix.c stack.c` */

Include C-libraries for input/output, allocation of memory, and string manipulation.

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

Include our own stack implementation header file stack.h.

#include "stack.h"

Task

Implement a postfix calculator for integer numbers. A postfix calculator reads expressions in in postfix notation. In this notation, the function symbol in an expression is notated behind the arguments. For instance, the infix expression 1 + 4 corresponds to (1, 4)+ in postfix notation. We will omit the syntactic sugar and write 1 4 +.

Expressions in postfix notation can be evaluated using a stack. For this exercise, implement a stack using a linked list and use it to store numbers. The stack should be stored in a separate header and implementation file (stack.c, stack.h).

You should read a mixture of integer numbers and operations (separated by white characters). Once = your program should print the result of the calculation and terminate. You may assume that an entered word will consist of at most 10 characters. To convert a string into a number you can use strtol or sscanf. You may assume that there are only correct inputs.

Your program should support the following operations: +, -, *, / and %.

Solution

int main() {

Create a stack structure and make a buffer to hold maximum 10 characters (plus null-termination).

    stack_handle_t stack = stack_create();
    char buffer[11];
    char *rest;
    scanf("%10s", buffer);

Loop until a = is read.

    while (strcmp(buffer, "=") != 0) {
        int a, b;

Each operation can be discriminated by the first character in the string buffer. The two operands are popped from the stack with stack_pop, and the result is put back on the stack with stack_push.

        switch (buffer[0]) {
            case '+':
                a = stack_pop(stack);
                b = stack_pop(stack);
                stack_push(stack, a + b);
                break;
            case '-':
                a = stack_pop(stack);
                b = stack_pop(stack);
                stack_push(stack, b - a);
                break;
            case '/':
                a = stack_pop(stack);
                b = stack_pop(stack);
                stack_push(stack, b / a);
                break;
            case '*':
                a = stack_pop(stack);
                b = stack_pop(stack);
                stack_push(stack, a * b);
                break;
            case '%':
                a = stack_pop(stack);
                b = stack_pop(stack);
                stack_push(stack, b % a);
                break;

If we cannot match an operation, we assume the input is a number. strtol tries to interpret the string as a number in base 13, and writes a pointer to the unrecognized rest of the string into rest.

            default:
                a = strtol(buffer, &rest, 10);

It is a valid number if the rest points to the null-termination at the end of the string, because the whole input has been recognized as a number.

                if (rest[0] == '\0') {
                    stack_push(stack, a);
                } else {
                    printf("ERROR: invalid number %s\n", buffer);
                }
        }

Read in the next number or operation.

        scanf("%10s", buffer);
    }

The result is the value on top of the stack. If the operations are unbalanced, we could have an empty stack here, but stack_pop then just returns 0.

    printf("%i\n", stack_pop(stack));

Don’t forget to free the memory.

    stack_destroy(stack);
    return 0;
}