QUESTION 07

Why are operators temporarily stored during infix conversion?

2 marks

Answer

Their output must wait until operands and higher-precedence or appropriate same-precedence operators have been processed.

Explain infix-to-postfix conversion using a stack with worked expressions.

5 marks

Answer in brief

Postfix places each operator after its operands. A stack preserves pending infix operators and parentheses during conversion.

Algorithm

Output each operand. Push an opening parenthesis.
On a closing parenthesis, output operators up to its matching opening parenthesis and discard the pair.
For an incoming operator, output stacked operators with higher precedence; also output equal-precedence ones when the incoming operator is left-associative.
Push the incoming operator. At the end, output remaining operators and reject unmatched parentheses.

Worked paper expressions

A + B - C * D * E / F - G becomes AB+CD*E*F/-G-. Multiplication and division are left-associative here. In the older paper’s A+B-C*D*E$F$G, interpret $ as the stated exponent operator with right associativity. The result is AB+CD*EFG$$*-. $ is notation for this exercise, not a standard C arithmetic operator.

Grouping example

(A+B)*C becomes AB+C*. The parentheses require A+B to complete before the multiplication. Postfix needs no grouping parentheses because operand/operator order already records that grouping.

Program limits

The complete converter accepts single ASCII letters or digits as operands, binary +, -, *, / and $, parentheses and spaces. It checks operand/operator order. It does not claim to parse unary minus, decimal numbers or multi-character variable names.

Complexity

Each token is read once and each operator is pushed and popped at most once, giving O(n) token work and O(n) stack/output space. Parentheses and associativity must be handled correctly; comparing precedence alone is insufficient.

Diagram or flowchart

CodeBhavya illustration of infix — Explain infix-to-postfix conversion using a stack with worked expressions. · Download diagram

Complete C example

main.c

Download main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <string.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 precedence(char op)
{
    if (op == '$') { return 3; }
    if (op == '*' || op == '/') { return 2; }
    if (op == '+' || op == '-') { return 1; }
    return 0;
}
int convert(const char input[], char output[80])
{
    char stack[80]; int top = -1, used = 0, need_operand = 1;
    for (int i = 0; input[i] != '\0'; ++i) {
        char ch = input[i];
        if (ch == ' ' || ch == '\t') { continue; }
        int operand = (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9');
        if (operand) {
            if (!need_operand) { return 0; }
            output[used++] = ch; need_operand = 0;
        } else if (ch == '(') {
            if (!need_operand) { return 0; }
            stack[++top] = ch;
        } else if (ch == ')') {
            if (need_operand) { return 0; }
            while (top >= 0 && stack[top] != '(') { output[used++] = stack[top--]; }
            if (top < 0) { return 0; }
            --top;
        } else if (precedence(ch) != 0) {
            if (need_operand) { return 0; }
            while (top >= 0 && stack[top] != '(' &&
                   (precedence(stack[top]) > precedence(ch) ||
                   (precedence(stack[top]) == precedence(ch) && ch != '$'))) {
                output[used++] = stack[top--];
            }
            stack[++top] = ch; need_operand = 1;
        } else { return 0; }
    }
    if (need_operand) { return 0; }
    while (top >= 0) { if (stack[top] == '(') { return 0; } output[used++] = stack[top--]; }
    output[used] = '\0'; return 1;
}

int main(void)
{
    char input[80], output[80];
    if (!read_line(input) || !convert(input, output)) { puts("Invalid expression"); return 1; }
    puts(output);
    return 0;
}

Sample input and output

Input

A+B-C*D*E/F-G

Output

AB+CD*E*F/-G-