QUESTION 09

In postfix evaluation, which popped value is the right operand?

2 marks

Answer

The first popped value is the right operand; the second is the left. This order is essential for subtraction and division.

Explain postfix evaluation using a stack with the supplied numerical expression.

5 marks

Answer in brief

A postfix evaluator stores completed operand values and replaces each operator’s operands with its result.

Algorithm

Read one token at a time. Push a numeric operand.
For a binary operator, require at least two stack values.
Pop right, then left; compute left operator right and push the result.
At the end, require exactly one result.

Worked trace

For 5 3 + 6 2 / * 3 5 * +: 5 and 3 give 8; 6 and 2 give 3 by integer division; 8 * 3 gives 24; 3 and 5 give 15; 24 + 15 gives 39. The answer is 39.

Invalid expressions

Reject insufficient operands, a zero divisor, unsupported tokens or more than one remaining value. An empty expression has no result. For 2 8 -, the result is -6, not 6, because the first popped value is 8 and belongs on the right.

Program limits

The supplied program uses whitespace-separated integer tokens and +, -, *, /. Each value and intermediate result is restricted to -1000000 through 1000000. The bound makes intermediate long long multiplication safe before the result check. It rejects out-of-range conversions and malformed tokens.

Complexity

Each of n tokens causes a fixed number of stack operations, giving O(n) token work after numeric token parsing. The stack can hold O(n) values. Parsing also depends on the total input-character count. The bounded demonstration buffer limits resource use without changing the underlying algorithm.

Complete C example

main.c

Download main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
int read_line(char s[80])
{
    if (fgets(s, 80, stdin) == NULL) { return 0; }
    char *newline = strchr(s, '\n');
    if (newline != NULL) { *newline = '\0'; return 1; }
    int ch = getchar();
    if (ch == '\n' || ch == EOF) { return 1; }
    while ((ch = getchar()) != '\n' && ch != EOF) { }
    return 0;
}
int evaluate(char input[], long long *out)
{
    long long stack[40]; int count = 0;
    char *token = strtok(input, " \t");
    while (token != NULL) {
        if (strlen(token) == 1 && strchr("+-*/", token[0]) != NULL) {
            if (count < 2) { return 0; }
            long long right = stack[--count], left = stack[--count], value;
            if (token[0] == '+') { value = left + right; }
            else if (token[0] == '-') { value = left - right; }
            else if (token[0] == '*') { value = left * right; }
            else { if (right == 0) { return 0; } value = left / right; }
            if (value < -1000000 || value > 1000000) { return 0; }
            stack[count++] = value;
        } else {
            char *end; errno = 0;
            long long value = strtoll(token, &end, 10);
            if (end == token || *end != '\0' || errno == ERANGE || value < -1000000 || value > 1000000 || count == 40) { return 0; }
            stack[count++] = value;
        }
        token = strtok(NULL, " \t");
    }
    if (count != 1) { return 0; }
    *out = stack[0]; return 1;
}

int main(void)
{
    char input[80];
    long long result;
    if (!read_line(input) || !evaluate(input, &result)) { puts("Invalid expression"); return 1; }
    printf("Result = %lld\n", result);
    return 0;
}

Sample input and output

Input

5 3 + 6 2 / * 3 5 * +

Output

Result = 39