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)
Nội dung chính
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.
- 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:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
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:
