Hôm nay cafedev chia sẻ cho ace một số ví dụ về việc sử dụng stack trong lập trình thực tế với các bài ví dụ hay và kinh điển. Trong phần ví dụ sẽ được code trên các ngôn ngữ khác nhau như C/C++, Java, Python….Nhằm giúp ace đang sử dụng các ngôn ngữ khác nhau hiểu nhanh và nắm vững cách dùng stack trong thực tế và khi đi làm.

Nếu ace nào chưa rõ về stack là gì?, có thể tham khảo series cấu trúc dữ liệu và giải thuật tham khảo đây..

Trong bài chúng ta sẽ áp dụng cấu trúc dữ liệu stack vào bài toán hoán đổi toán tử trong một phép toán.(Infix to Postfix)

1. Khái niệm về hoán đổi toán tử(Infix to Postfix)

Biểu thức Infix: Biểu thức có dạng a toán tử b. Khi một toán tử ở giữa mọi cặp toán hạng.

Biểu thức Postfix: Biểu thức có dạng a b toán tử. Khi một toán tử được theo sau cho mọi cặp toán hạng.

Trình biên dịch quét biểu thức từ trái sang phải hoặc từ phải sang trái.

Hãy xem xét biểu thức dưới đây: a op1 b op2 c op3 d

Nếu op1 bằng +, op2 bằng *, op3 bằng +

Đầu tiên trình biên dịch sẽ quét biểu thức để đánh giá biểu thức b * c, sau đó quét lại biểu thức để thêm a vào biểu thức đó. Kết quả sau đó được thêm vào d sau một lần quét khác.

Việc quét lặp đi lặp lại thì rất hiệu quả. Tốt hơn là chuyển biểu thức sang dạng hậu tố (hoặc tiền tố) trước khi đánh giá.

Biểu thức tương ứng ở dạng postfix là: abc * + d +. Các biểu thức postfix có thể được đánh giá dễ dàng bằng cách sử dụng một stack.

  1. Thuật toán(Algorithm)

1. Quét biểu thức infix từ trái sang phải.

2. Nếu ký tự được quét là một toán hạng, hãy xuất ra.

3. Nếu Khác,

… ..3.1 Nếu mức ưu tiên của toán tử được quét lớn hơn mức ưu tiên của toán tử trong stack (hoặc stack trống hoặc stack chứa dấu ‘(‘), push nó.

… ..3.2 Nếu Khác, thì Pop tất cả các toán tử từ stack lớn hơn hoặc bằng được ưu tiên hơn so với toán tử được quét. Sau khi thực hiện điều đó push toán tử đã quét vào stack. (Nếu bạn gặp phải dấu ngoặc đơn trong khi xuất hiện thì hãy dừng lại ở đó và push toán tử đã quét vào stack.)

4. Nếu ký tự được quét là một dấu ‘(‘, hãy push nó vào stack.

5. Nếu ký tự được quét là dấu ‘)’, hãy mở stack và xuất nó cho đến khi gặp dấu ‘(‘ và loại bỏ cả hai dấu ngoặc đơn.

6. Lặp lại các bước 2-6 cho đến khi biểu thức infix được quét.

7. In đầu ra

8. Pop và xuất từ ​​stack cho đến khi nó không trống.

2. Code ví dụ

Sau đây là việc thực hiện thuật toán trên:

C++

/* C++ implementation to convert infix expression to postfix*/
// Note that here we use std::stack  for Stack operations 
#include<bits/stdc++.h> 
using namespace std; 
  
//Function to return precedence of operators 
int prec(char c) 
{ 
    if(c == '^') 
    return 3; 
    else if(c == '*' || c == '/') 
    return 2; 
    else if(c == '+' || c == '-') 
    return 1; 
    else
    return -1; 
} 
  
// The main function to convert infix expression 
//to postfix expression 
void infixToPostfix(string s) 
{ 
    std::stack<char> st; 
    st.push('N'); 
    int l = s.length(); 
    string ns; 
    for(int i = 0; i < l; i++) 
    { 
        // If the scanned character is an operand, add it to output string. 
        if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z')) 
        ns+=s[i]; 
  
        // If the scanned character is an ‘(‘, push it to the stack. 
        else if(s[i] == '(') 
          
        st.push('('); 
          
        // If the scanned character is an ‘)’, pop and to output string from the stack 
        // until an ‘(‘ is encountered. 
        else if(s[i] == ')') 
        { 
            while(st.top() != 'N' && st.top() != '(') 
            { 
                char c = st.top(); 
                st.pop(); 
               ns += c; 
            } 
            if(st.top() == '(') 
            { 
                char c = st.top(); 
                st.pop(); 
            } 
        } 
          
        //If an operator is scanned 
        else{ 
            while(st.top() != 'N' && prec(s[i]) <= prec(st.top())) 
            { 
                char c = st.top(); 
                st.pop(); 
                ns += c; 
            } 
            st.push(s[i]); 
        } 
  
    } 
    //Pop all the remaining elements from the stack 
    while(st.top() != 'N') 
    { 
        char c = st.top(); 
        st.pop(); 
        ns += c; 
    } 
      
    cout << ns << endl; 
  
} 
  
//Driver program to test above functions 
int main() 
{ 
    string exp = "a+b*(c^d-e)^(f+g*h)-i"; 
    infixToPostfix(exp); 
    return 0; 
} 

C:


// C program to convert infix expression to postfix  
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
  
// Stack type 
struct Stack 
{ 
    int top; 
    unsigned capacity; 
    int* array; 
}; 
  
// Stack Operations 
struct Stack* createStack( unsigned capacity ) 
{ 
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack)); 
  
    if (!stack)  
        return NULL; 
  
    stack->top = -1; 
    stack->capacity = capacity; 
  
    stack->array = (int*) malloc(stack->capacity * sizeof(int)); 
  
    return stack; 
} 
int isEmpty(struct Stack* stack) 
{ 
    return stack->top == -1 ; 
} 
char peek(struct Stack* stack) 
{ 
    return stack->array[stack->top]; 
} 
char pop(struct Stack* stack) 
{ 
    if (!isEmpty(stack)) 
        return stack->array[stack->top--] ; 
    return '$'; 
} 
void push(struct Stack* stack, char op) 
{ 
    stack->array[++stack->top] = op; 
} 
  
  
// A utility function to check if the given character is operand 
int isOperand(char ch) 
{ 
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'); 
} 
  
// A utility function to return precedence of a given operator 
// Higher returned value means higher precedence 
int Prec(char ch) 
{ 
    switch (ch) 
    { 
    case '+': 
    case '-': 
        return 1; 
  
    case '*': 
    case '/': 
        return 2; 
  
    case '^': 
        return 3; 
    } 
    return -1; 
} 
  
  
// The main function that converts given infix expression 
// to postfix expression.  
int infixToPostfix(char* exp) 
{ 
    int i, k; 
  
    // Create a stack of capacity equal to expression size  
    struct Stack* stack = createStack(strlen(exp)); 
    if(!stack) // See if stack was created successfully  
        return -1 ; 
  
    for (i = 0, k = -1; exp[i]; ++i) 
    { 
        // If the scanned character is an operand, add it to output. 
        if (isOperand(exp[i])) 
            exp[++k] = exp[i]; 
          
        // If the scanned character is an ‘(‘, push it to the stack. 
        else if (exp[i] == '(') 
            push(stack, exp[i]); 
          
        // If the scanned character is an ‘)’, pop and output from the stack  
        // until an ‘(‘ is encountered. 
        else if (exp[i] == ')') 
        { 
            while (!isEmpty(stack) && peek(stack) != '(') 
                exp[++k] = pop(stack); 
            if (!isEmpty(stack) && peek(stack) != '(') 
                return -1; // invalid expression              
            else
                pop(stack); 
        } 
        else // an operator is encountered 
        { 
            while (!isEmpty(stack) && Prec(exp[i]) <= Prec(peek(stack))) 
                exp[++k] = pop(stack); 
            push(stack, exp[i]); 
        } 
  
    } 
  
    // pop all the operators from the stack 
    while (!isEmpty(stack)) 
        exp[++k] = pop(stack ); 
  
    exp[++k] = '\0'; 
    printf( "%s", exp ); 
} 
  
// Driver program to test above functions 
int main() 
{ 
    char exp[] = "a+b*(c^d-e)^(f+g*h)-i"; 
    infixToPostfix(exp); 
    return 0; 
} 

Java


/* Java implementation to convert infix expression to postfix*/
// Note that here we use Stack class for Stack operations 
  
import java.util.Stack; 
  
class Test 
{ 
    // A utility function to return precedence of a given operator 
    // Higher returned value means higher precedence 
    static int Prec(char ch) 
    { 
        switch (ch) 
        { 
        case '+': 
        case '-': 
            return 1; 
       
        case '*': 
        case '/': 
            return 2; 
       
        case '^': 
            return 3; 
        } 
        return -1; 
    } 
       
    // The main method that converts given infix expression 
    // to postfix expression.  
    static String infixToPostfix(String exp) 
    { 
        // initializing empty String for result 
        String result = new String(""); 
          
        // initializing empty stack 
        Stack<Character> stack = new Stack<>(); 
          
        for (int i = 0; i<exp.length(); ++i) 
        { 
            char c = exp.charAt(i); 
              
             // If the scanned character is an operand, add it to output. 
            if (Character.isLetterOrDigit(c)) 
                result += c; 
               
            // If the scanned character is an '(', push it to the stack. 
            else if (c == '(') 
                stack.push(c); 
              
            //  If the scanned character is an ')', pop and output from the stack  
            // until an '(' is encountered. 
            else if (c == ')') 
            { 
                while (!stack.isEmpty() && stack.peek() != '(') 
                    result += stack.pop(); 
                  
                if (!stack.isEmpty() && stack.peek() != '(') 
                    return "Invalid Expression"; // invalid expression                 
                else
                    stack.pop(); 
            } 
            else // an operator is encountered 
            { 
                while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())){ 
                    if(stack.peek() == '(') 
                        return "Invalid Expression"; 
                    result += stack.pop(); 
             } 
                stack.push(c); 
            } 
       
        } 
       
        // pop all the operators from the stack 
        while (!stack.isEmpty()){ 
            if(stack.peek() == '(') 
                return "Invalid Expression"; 
            result += stack.pop(); 
         } 
        return result; 
    } 
    
    // Driver method  
    public static void main(String[] args)  
    { 
        String exp = "a+b*(c^d-e)^(f+g*h)-i"; 
        System.out.println(infixToPostfix(exp)); 
    } 
} 

Python

# Python program to convert infix expression to postfix 
  
# Class to convert the expression 
class Conversion: 
      
    # Constructor to initialize the class variables 
    def __init__(self, capacity): 
        self.top = -1 
        self.capacity = capacity 
        # This array is used a stack  
        self.array = [] 
        # Precedence setting 
        self.output = [] 
        self.precedence = {'+':1, '-':1, '*':2, '/':2, '^':3} 
      
    # check if the stack is empty 
    def isEmpty(self): 
        return True if self.top == -1 else False
      
    # Return the value of the top of the stack 
    def peek(self): 
        return self.array[-1] 
      
    # Pop the element from the stack 
    def pop(self): 
        if not self.isEmpty(): 
            self.top -= 1
            return self.array.pop() 
        else: 
            return "$"
      
    # Push the element to the stack 
    def push(self, op): 
        self.top += 1
        self.array.append(op)  
  
    # A utility function to check is the given character 
    # is operand  
    def isOperand(self, ch): 
        return ch.isalpha() 
  
    # Check if the precedence of operator is strictly 
    # less than top of stack or not 
    def notGreater(self, i): 
        try: 
            a = self.precedence[i] 
            b = self.precedence[self.peek()] 
            return True if a  <= b else False
        except KeyError:  
            return False
              
    # The main function that converts given infix expression 
    # to postfix expression 
    def infixToPostfix(self, exp): 
          
        # Iterate over the expression for conversion 
        for i in exp: 
            # If the character is an operand,  
            # add it to output 
            if self.isOperand(i): 
                self.output.append(i) 
              
            # If the character is an '(', push it to stack 
            elif i  == '(': 
                self.push(i) 
  
            # If the scanned character is an ')', pop and  
            # output from the stack until and '(' is found 
            elif i == ')': 
                while( (not self.isEmpty()) and self.peek() != '('): 
                    a = self.pop() 
                    self.output.append(a) 
                if (not self.isEmpty() and self.peek() != '('): 
                    return -1
                else: 
                    self.pop() 
  
            # An operator is encountered 
            else: 
                while(not self.isEmpty() and self.notGreater(i)): 
                    self.output.append(self.pop()) 
                self.push(i) 
  
        # pop all the operator from the stack 
        while not self.isEmpty(): 
            self.output.append(self.pop()) 
  
        print "".join(self.output) 
  
# Driver program to test above function 
exp = "a+b*(c^d-e)^(f+g*h)-i"
obj = Conversion(len(exp)) 
obj.infixToPostfix(exp) 

C#

using System; 
using System.Collections.Generic; 
  
/* c# implementation to convert infix expression to postfix*/
// Note that here we use Stack class for Stack operations  
  
public  class Test 
{ 
    // A utility function to return precedence of a given operator  
    // Higher returned value means higher precedence  
    internal static int Prec(char ch) 
    { 
        switch (ch) 
        { 
        case '+': 
        case '-': 
            return 1; 
  
        case '*': 
        case '/': 
            return 2; 
  
        case '^': 
            return 3; 
        } 
        return -1; 
    } 
  
    // The main method that converts given infix expression  
    // to postfix expression.   
    public static string infixToPostfix(string exp) 
    { 
        // initializing empty String for result  
        string result = ""; 
  
        // initializing empty stack  
        Stack<char> stack = new Stack<char>(); 
  
        for (int i = 0; i < exp.Length; ++i) 
        { 
            char c = exp[i]; 
  
             // If the scanned character is an operand, add it to output.  
            if (char.IsLetterOrDigit(c)) 
            { 
                result += c; 
            } 
  
            // If the scanned character is an '(', push it to the stack.  
            else if (c == '(') 
            { 
                stack.Push(c); 
            } 
  
            //  If the scanned character is an ')', pop and output from the stack   
            // until an '(' is encountered.  
            else if (c == ')') 
            { 
                while (stack.Count > 0 && stack.Peek() != '(') 
                { 
                    result += stack.Pop(); 
                } 
  
                if (stack.Count > 0 && stack.Peek() != '(') 
                { 
                    return "Invalid Expression"; // invalid expression 
                } 
                else
                { 
                    stack.Pop(); 
                } 
            } 
            else // an operator is encountered 
            { 
                while (stack.Count > 0 && Prec(c) <= Prec(stack.Peek())) 
                { 
                    result += stack.Pop(); 
                } 
                stack.Push(c); 
            } 
  
        } 
  
        // pop all the operators from the stack  
        while (stack.Count > 0) 
        { 
            result += stack.Pop(); 
        } 
  
        return result; 
    } 
  
    // Driver method   
    public static void Main(string[] args) 
    { 
        string exp = "a+b*(c^d-e)^(f+g*h)-i"; 
        Console.WriteLine(infixToPostfix(exp)); 
    } 
} 

Kết quả:

abcd^e-fgh*+^*+i-

Nguồn và Tài liệu tiếng anh tham khảo:

Tài liệu từ cafedev:

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!