Data Structures - Expression Parsing

Expression parsing is the most classic application scenario of the stack data structure.

Expression parsing demonstrates how to use stacks to handle conversions among infix, prefix, and postfix expressions, as well as expression evaluation.

Three Forms of Expressions

Infix expression A + B * C to postfix expression — step-by-step demonstration

Step 1Read AOperand, output directlyOutput: AStack: empty

Step 2Read +Operator, push onto stackOutput: AStack: +

Step 3Read BOperand, output directlyOutput: ABStack: +

Step 4Read ** has higher precedence than +, push onto stackOutput: ABStack: +*

Step 5Read COperand, output directlyOutput: ABCStack: +*

Step 6EndPop all operators from the stackOutput: ABC*+Stack: empty

Final result: A + B * C → A B C * +

When processing mathematical expressions in a computer, there are three representation methods:

Type	Operator position	Example	Evaluation difficulty	Parentheses requirement
Infix expression	Between operands (human convention)	`A + B * C`	Need to handle precedence and parentheses	Needed
Prefix expression(Polish notation)	Before operands	`+ A * B C`	Single scan is enough	Not needed
Postfix expression(Reverse Polish notation)	After operands	`A B C * +`	Single scan is enough	Not needed

The biggest advantage of postfix and prefix expressions is that during evaluation there is no need to consider operator precedence or parentheses; you only need to scan sequentially from left to right.

Infix to Postfix Algorithm (Shunting Yard Algorithm Idea)

The core algorithm for converting an infix expression to a postfix expression is implemented with a stack. The basic process is as follows:

Scan the infix expression from left to right
When encounteringan operand(digit/letter), output it directly
When encounteringan operator, compare its precedence with the operator on the top of the stack:
- If the operator on the top of the stack has higher or equal precedence, pop the top and output it
- Repeat this process until the current operator can be pushed onto the stack
When encounteringa left parenthesis, push it directly onto the stack
When encounteringa right parenthesis, keep popping operators from the top of the stack and outputting them until a left parenthesis is encountered (the left parenthesis is popped but not output)
After the scan ends, pop and output the remaining operators in the stack one by one

Example

#include <stdio.h>
#include <ctype.h> /* isalnum function */
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) { stack[++top] = c; }
char pop() { return (top == -1) ? -1 : stack[top--]; }

/* Returns operator precedence: higher number means higher precedence */
int precedence(char op) {
if (op == '+' || op == '-') return 1; /* Addition and subtraction have the lowest precedence */
if (op == '*' || op == '/') return 2; /* Multiplication and division have higher precedence */
if (op == '^') return 3; /* Exponentiation has the highest precedence */
return 0; /* Not an operator */
}

Infix expression to postfix expression
Parameters: infix - the input infix expression string
postfix - the output postfix expression buffer */
void infixToPostfix(char* infix, char* postfix) {
int i = 0, j = 0;
char c;

while ((c = infix[i++]) != '\0') {
/* Operand (letter or digit): output directly */
if (isalnum(c)) {
postfix[j++] = c;
}
/* Left parenthesis: push directly */
else if (c == '(') {
push(c);
}
/* Right parenthesis: pop until left parenthesis is encountered */
else if (c == ')') {
while (top != -1 && stack[top] != '(') {
postfix[j++] = pop();
}
pop(); /* Pop left parenthesis '(' but do not output */
}
/* Operator: handle precedence */
else {
while (top != -1 &&
precedence(stack[top]) >= precedence(c) &&
stack[top] != '(') {
postfix[j++] = pop();
}
push(c);
}
}

/* Pop all remaining operators from the stack */
while (top != -1) {
postfix[j++] = pop();
}
postfix[j] = '\0'; /* End of string */
}

int main() {
char infix[] = "A+B*C";
char postfix[MAX];

infixToPostfix(infix, postfix);
printf("Infix: %s\n", infix); /* Output: Infix: A+B*C */
printf("Postfix: %s\n", postfix); /* Output: Postfix: ABC*+ */
return 0;
}

Postfix Expression Evaluation

Postfix expression 5 3 + 2 * evaluation — step demonstration

Step 1Read 5Number, push onto stackStack: 5

Step 2Read 3Number, push onto stackStack: 5 3

Step 3Read +Pop 3 and 5, compute 5+3=8, push result onto stackStack: 85+3=8

Step 4Read 2Number, push onto stackStack: 8 2

Step 5Read *Pop 2 and 8, compute 8*2=16, push result onto stackStack: 168*2=16

ResultEndOnly 16 remains on the stack, which is the calculated resultResult = 16

Postfix 53+2* = 16 (equivalent to infix (5+3)*2)

With the postfix expression, evaluating using a stack is very straightforward: push operands onto the stack; when encountering an operator, pop two operands, compute, and push the result back.

Example

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

#define MAX 100

int stack[MAX];
int top = -1;

void push(int val) { stack[++top] = val; }
int pop() { return stack[top--]; }

/* Calculate the value of the postfix expression
Parameters: postfix - postfix expression (operands are single digits 0-9)
Return value: the calculated result of the expression */
int evaluatePostfix(char* postfix) {
int i = 0;
char c;

while ((c = postfix[i++]) != '\0') {
/* Operand: convert to number and push onto stack */
if (isdigit(c)) {
push(c - '0'); /* '3' converted to integer 3 */
}
/* Operator: pop two operands, compute, and push back */
else {
int b = pop(); /* Second operand (right operand) */
int a = pop(); /* First operand (left operand) */
switch (c) {
case '+': push(a + b); break;
case '-': push(a - b); break;
case '*': push(a * b); break;
case '/': push(a / b); break;
}
}
}
return pop(); /* The last element on the stack is the final result */
}

int main() {
/* Postfix expression "23+5*" is equivalent to infix "(2+3)*5" = 25 */
char postfix[] = "23+5*";
int result = evaluatePostfix(postfix);
printf("Postfix %s = %d\n", postfix, result); /* Output: Postfix 23+5* = 25 */
return 0;
}

When evaluating a postfix expression, the pop order of operands is critical: the first popped isright operand(b), and the later popped isleft operand(a). This is especially important for non-commutative operations like subtraction and division; reversing the order will produce incorrect results.

Complete Example: Infix Evaluation

Chaining the above two steps together yields a complete calculator: infix → postfix → evaluation.

Example

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

#define MAX 100

/* Operator precedence helper function (same as above), evaluation function (same as above), conversion function (same as above) */
/* For brevity, the functions defined above are omitted here; include them when actually using */

int main() {
char infix[] = "5+3*2"; /* Infix expression */
char postfix[MAX];
infixToPostfix(infix, postfix); /* Step 1: Convert to postfix */

printf("Infix: %s\n", infix); /* Output: Infix: 5+3*2 */
printf("Postfix: %s\n", postfix); /* Output: Postfix: 532*+ */

int result = evaluatePostfix(postfix); /* Step 2: Evaluate */
printf("Result: %s = %d\n", infix, result);
/* Output: Result: 5+3*2 = 11 */
return 0;
}

Other extensions