[DSA] Chuyển biểu thức trung tố sang hậu tố

Để chuyển đổi một biểu thức trung tố thành hậu tố, ta có thể sử dụng cấu trúc dữ liệu Stack. Cách thức hoạt động như sau:

• Duyệt từng phần tử trong biểu thức trung tố từ trái sang phải.
• Nếu phần tử đó là toán hạng, ta đưa nó vào kết quả đầu ra.
• Nếu phần tử đó là toán tử, ta đưa nó vào Stack.
• Nếu phần tử đó là dấu mở ngoặc, ta đưa nó vào Stack.
• Nếu phần tử đó là dấu đóng ngoặc, ta lấy các phần tử trong Stack và đưa vào kết quả đầu ra cho đến khi gặp dấu mở ngoặc. Khi đó, ta loại bỏ cả dấu mở ngoặc và dấu đóng ngoặc.
• Khi đã duyệt hết các phần tử, ta lấy tất cả các phần tử trong Stack và đưa vào kết quả đầu ra. 

Tham khảo code sau: (code này chưa được kiểm tra kỹ nhiều trường hợp đặc biệt)

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

#include <string.h>

typedef struct {

int *items;

int top;

int size;

} Stack;

Stack *createStack(int size) {

Stack *stack = (Stack *)malloc(sizeof(Stack));

stack->items = (int *)malloc(size * sizeof(int));

stack->top = -1;

stack->size = size;

return stack;

}

void destroyStack(Stack *stack) {

free(stack->items);

free(stack);

}

void push(Stack *stack, int item) {

if (stack->top == stack->size - 1) {

printf("Stack Overflow!\n");

return;

}

stack->items[++stack->top] = item;

}

int pop(Stack *stack) {

if (stack->top == -1) {

printf("Stack Underflow!\n");

return -1;

}

return stack->items[stack->top--];

}

int peek(Stack *stack) {

if (stack->top == -1) {

printf("Stack is empty!\n");

return -1;

}

return stack->items[stack->top];

}

int isEmpty(Stack *stack) {

return stack->top == -1;

}

int precedence(char operator) {

if (operator == '*' || operator == '/')

return 2;

else if (operator == '+' || operator == '-')

return 1;

else

return 0;

}

void infixToPostfix(char *infix, char *postfix) {

Stack *stack = createStack(strlen(infix));

int i = 0, j = 0;

char ch;

while ((ch = infix[i++]) != '\0') {

if (isalnum(ch)) {

postfix[j++] = ch;

} else if (ch == '(') {

push(stack, ch);

} else if (ch == ')') {

while (!isEmpty(stack) && peek(stack) != '(') {

postfix[j++] = pop(stack);

}

pop(stack);

} else {

while (!isEmpty(stack) && precedence(ch) <= precedence(peek(stack))) {

postfix[j++] = pop(stack);

}

push(stack, ch);

}

}

while (!isEmpty(stack)) {

postfix[j++] = pop(stack);

}

postfix[j] = '\0';

destroyStack(stack);

}

int main() {

char infix[100];

char postfix[100];

// Test case 1

strcpy(infix, "5+3*2");

infixToPostfix(infix, postfix);

printf("Infix: %s\nPostfix: %s\n\n", infix, postfix);

// Test case 2

strcpy(infix, "1+2+3+4");

infixToPostfix(infix, postfix);

printf("Infix: %s\nPostfix: %s\n\n", infix, postfix);

// Test case 3

strcpy(infix, "(2+3)*4");

infixToPostfix(infix, postfix);

printf("Infix: %s\nPostfix: %s\n\n", infix, postfix);

// Test case 4

strcpy(infix, "8/(2+2)-3*2");

infixToPostfix(infix, postfix);

printf("Infix: %s\nPostfix: %s\n\n", infix, postfix);

// Test case 5

strcpy(infix, "3^2-2^3*4+5");

infixToPostfix(infix, postfix);

printf("Infix: %s\nPostfix: %s\n\n", infix, postfix);

// Test case 6

strcpy(infix, "2*(4+5)/3");

infixToPostfix(infix, postfix);

printf("Infix: %s\nPostfix: %s\n\n", infix, postfix);

// Test case 7

strcpy(infix, "1+2-3*4/5^6");

infixToPostfix(infix, postfix);

printf("Infix: %s\nPostfix: %s\n\n", infix, postfix);

// Test case 8

strcpy(infix, "3*2+4*5");

infixToPostfix(infix, postfix);

printf("Infix: %s\nPostfix: %s\n\n", infix, postfix);

// Test case 9

strcpy(infix, "2^3^2");

infixToPostfix(infix, postfix);

printf("Infix: %s\nPostfix: %s\n\n", infix, postfix);

// Test case 10

strcpy(infix, "3+(2+1)*2^3^2-8/(5-1*2/2)");

infixToPostfix(infix, postfix);

printf("Infix: %s\nPostfix: %s\n\n", infix, postfix);

return 0;

}