VIẾT CHƯƠNG TRÌNH TÍNH GIÁ TRỊ BIỂU THỨC
Tác giả: Đặng Nhật Anh
Cấp độ bài viết: Trung bình
Tóm tắt: Bài tut này có mục đích hướng dẫn các bạn tự viết ra một chương trình tính giá trị biểu
thức toán học đơn giản bằng một số kỹ thuật căn bản
Bài hướng dẫn này bao gồm 3 phần: 1. Ngăn xếp và cách tạo lập; 2. Ký pháp Nghịch đảo Ba
Lan; 3. Viết chương trình. Cả ba phần sẽ được để trong cùng một bài viết cho liên tục.
Phần 1 - Ngăn xếp và cách tạo lập
I. Giới thiệu
Ngăn xếp (stack) là một loại cấu trúc dữ liệu tuân theo quy tắc Last In, First Out (LIFO, tức
vào sau cùng, ra trước tiên). Có thể hình dung ngăn xếp như một chồng sách mà mỗi quyển sách
là một phần tử dữ liệu. Quyển sách để lên trên cùng (tức quyển sau cùng) sẽ được lấy ra đầu tiên,
quyển được bỏ vào đầu tiên thì lấy ra sau cùng.
Ngăn xếp có nhiều ứng dụng trong lập trình, đặc biệt là trong các trình xử lý biểu thức, cây cú
pháp, v.v.
Có thể tìm hiểu thêm về ngăn xếp ở Wikipedia. http://vi.wikipedia.org/wiki/Ng%C4%83n_x
%E1%BA%BFp
II. Phương thức và thuộc tính
Theo mặc định, ngăn xếp có hai phương thức (còn gọi là phép toán) chính yếu:
Push: bỏ một phần tử vào ngăn xếp, ở vị trí trên cùng (sau cùng).
Pop: lấy phần tử trên cùng (sau cùng) ra khỏi ngăn xếp, trả về giá trị của phần tử đó.
Ngoài ra, người ta còn có thể thêm một phương thức nữa:
Peek: trả về giá trị phần tử trên cùng của ngăn xếp nhưng không lấy nó ra khỏi ngăn xếp.
Thuộc tính Length của ngăn xếp cho biết độ lớn của nó. Nếu ngăn xếp không có phần tử nào, ta
có Length = 0.
III. Tạo lập
Trong VB6 mặc nhiên không có kiểu dữ liệu ngăn xếp. Do đó ta sẽ tự tạo.
Trên lý thuyết, các phần tử trong ngăn xếp có thể có một kiểu bất kỳ. Trong ví dụ sau đây, chúng
ta sẽ làm một ngăn xếp chứa các số nguyên, đặt tên là IntStack.
Ta tạo ngăn xếp bằng một class, có 3 phương thức Push, Pop, Peek và 1 thuộc tính Length.
Đoạn mã của class sẽ như sau:

Nodes(Ptr) = 0
Ptr = Ptr - 1 'Đẩy con trỏ xuống
Else
'Báo lỗi Stack Empty
Pop = 0
End If
End Function

' Phương thức Peek
Public Function Peek() As Integer
If Ptr > 0 Then
' Trả về phần tử trên cùng
Peek = Nodes(Ptr)
Else
'Báo lỗi Stack Empty
Peek = 0
End If
End Function
2

' Thuộc tính Length
Public Property Get Length() As Integer
Length = Ptr
End Property
Bạn thử kiểm tra bằng đoạn mã sau:
Dim stack As New IntStack
stack.Push 8
stack.Push 3
MsgBox stack.Pop()
MsgBox stack.Peek()

• Nếu gặp toán tử, tạm gọi là opCurrent, kiểm tra xem toán tử trên cùng của oprStack có
mức ưu tiên cao hơn hoặc bằng opCurrent hay không. Nếu có thì pop nó push vào
rpnStack, cứ vậy hoài cho tới khi gặp một toán tử có mức ưu tiên nhỏ hơn opCurrent,
hoặc khi oprStack trống rỗng, thì dừng, bấy giờ push opCurrent vào oprStack. Mức ưu
tiên toán tử (thấp lên cao): dấu ngoặc < cộng, trừ < nhân chia < lũy thừa < dấu âm/dương
(cộng trừ đơn phân).
• Cuối cùng, lần lượt pop các phần tử trong oprStack và push vào rpnStack cho tới hết.
Vì dấu âm dương và dấu cộng trừ giống nhau nên khi gặp phải thì cần phân biệt. Nếu trước nó là
dấu ( hoặc một toán tử thì nó là dấu âm dương, nếu trước nó là dấu ) hoặc một toán hạng thì nó là
dấu cộng trừ.
III. Trình tự tính toán
Tạo một ngăn xếp nữa gọi là ResultStack.
Xét từng phần tử của rpnStack, từ thấp lên cao (từ đầu về cuối).
• Nếu gặp toán hạng thì push vào ResultStack.
• Nếu gặp toán tử nhị phân, pop hai phần tử từ ResultStack, thực hiện phép toán, push kết
quả trở lại ResultStack.
• Nếu gặp toán tử đơn phân, pop một phần tử từ ResultStack, thực hiện phép toán, push kết
quả trở lại ResultStack.
Kết quả cuối cùng là phần tử trên cùng của ResultStack.
Tham khảo thêm: http://en.wikipedia.org/wiki/Reverse_Polish_notation
4
Phần 3 - Viết chương trình
I. Định hình
Khả năng của chương trình là tính được các phép toán cộng, trừ, nhân, chia, lũy thừa, âm dương
trên hệ số thực.
Chương trình của chúng ta sẽ có một TextBox gọi là txtExpression để nhập biểu thức, một
TextBox là txtResult chứa kết quả, cùng một Command Button là cmdEvaluate để tính toán.
Vậy ta cần một module (MainModule) để chứa các hàm cần thiết cho việc xử lý chuỗi biểu thức
và tính giá trị, một class làm ngăn xếp và ngăn xếp này chứa các phần tử kiểu String
(StringStack).

Public Function Peek() As String
If Ptr >= 0 Then
Peek = Nodes(Ptr)
5
Else
Peek = ""
End If
End Function

' Ngăn xếp tiêu chuẩn không có phương thức này,
' nhưng ta thêm vào để giúp cho việc tính toán
Public Function GetAt(ByVal Position As Integer) As String
GetAt = Nodes(Position + 1)
End Function
Tạo module, đặt là MainModule và biên vào đoạn mã sau đây:
Option Explicit

' Loại bỏ các khoảng trắng không cần thiết khỏi biểu thức
Private Function EliminateWhite(ByVal sExpr As String) As String
Dim s As String
s = Replace(sExpr, " ", "")
s = Replace(s, vbTab, "")
EliminateWhite = s
End Function

' Kiểm tra xem tham số đưa vào có phải là toán tử hay không,
' ngoại trừ dấu ")"
' Ta dùng hàm này để phân biệt dấu âm dương với dấu cộng trừ
Private Function IsOperator(ByVal token As String) As Boolean
Const sOp As String = "(+-*/^" ' Không có ")"

iPos = iPos + 1
Loop
End If
' Kết hợp phần nguyên và phần thập phân (nếu có)
sValue = sInt & IIf(bIsInt, "", "." & sDec)
GetNumber = Val(sValue) ' Trả về giá trị Double
End Function

' Tính mức ưu tiên toán tử
Private Function OprPrec(ByVal op As String) As Byte
Select Case op
Case "(", ")"
OprPrec = 0
Case "+", "-"
OprPrec = 1
Case "*", "/"
OprPrec = 2
Case "^"
OprPrec = 3
Case "u+", "u-" 'Toán tử đơn phân (unary plus, unary minus)
OprPrec = 4
Case Else
End Select
End Function

' Biến biểu thức thành một mảng các token (mỗi token là một toán tử hay toán
hạng)
Private Sub Tokenise(ByVal sExpr As String, Tokens() As String)
Dim sResult(255) As String
Dim iToken As Integer

If Trim$(sExpr) = vbNullString Then
ExprEval = 0: Exit Function
End If

' Loại bỏ khoảng trắng dư thừa
sExpr = EliminateWhite(sExpr)

' Thêm ký tự NULL vào cuối biểu thức để báo kết thúc
sExpr = sExpr & Chr$(0)

' Hai ngăn xếp cần cho chuyển đổi
Dim rpnStack As New StringStack
Dim oprStack As New StringStack

'##### Chuyển đổi #####

' Mảng chứa các token
Dim Tokens() As String

' Thiết lập mảng token
Tokenise sExpr, Tokens

' Toán tử tạm thời
Dim tmpOp As String

Dim i As Integer
For i = 0 To UBound(Tokens)
Select Case Tokens(i)
Case "("
oprStack.Push Tokens(i)

End If
If oprStack.Length > 0 Then
Do While OprPrec(oprStack.Peek) >=
OprPrec(tmpOp)
rpnStack.Push oprStack.Pop
Loop
oprStack.Push tmpOp
Else
oprStack.Push tmpOp
End If
Case "^", "*", "/"
If oprStack.Length > 0 Then
Do While OprPrec(oprStack.Peek) >=
OprPrec(Tokens(i))
rpnStack.Push oprStack.Pop
Loop
oprStack.Push Tokens(i)
Else
oprStack.Push Tokens(i)
End If
Case Else
rpnStack.Push Tokens(i)
End Select
tmpOp = ""
Next i

' Xả hết từ oprStack vào rpnStack
Do While oprStack.Length > 0
rpnStack.Push oprStack.Pop
Loop

ResultStack.Push CStr(a / b)
Else
MsgBox "Chia cho 0", vbCritical,"Loi"
Exit Function
End If
Case "+"
b = Val(ResultStack.Pop)
a = Val(ResultStack.Pop)
ResultStack.Push CStr(a + b)
Case "-"
b = Val(ResultStack.Pop)
a = Val(ResultStack.Pop)
ResultStack.Push CStr(a - b)
Case Else
ResultStack.Push rpnStack.GetAt(j)
End Select
Next j
ReturnValue:
ExprEval = Val(ResultStack.Pop)
End Function
Trong sự kiện click của cmdEvaluate, ta ghi:
Private Sub cmdEvaluate_Click()
txtResult.Text = ExprEval(txtExpression.Text)
End Sub
Lưu project và chạy thử. Bạn nhập vào một biểu thức đại loại như ((1 + 2) * 4) + 3 và bấm nút
Tính để thấy kết quả.
Kết luận
Bài hướng dẫn đã giới thiệu đến quý vị một số khái niệm căn bản trong kỹ thuật xử lý chuỗi biểu
thức, cũng như chỉ dẫn cách viết một chương trình tính giá trị biểu thức đơn giản.
Chương trình còn một vài chỗ cần mở rộng, như bộ bẫy lỗi và báo lỗi, xử lý số dạng Hexa (vd:

8. sExpr = EliminateWhite(sExpr)
9.
10. sExpr = sExpr & Chr$(0)
11.
11
12. Dim rpnStack As New Collection 'Thay đổi
13. Dim oprStack As New Collection 'Thay đổi
14.
15. '##### Chuyen doi #####
16.
17. Dim Tokens() As String
18.
19. Tokenise sExpr, Tokens
20.
21. Dim tmpOp As String
22.
23. Dim i As Integer
24. For i = 0 To UBound(Tokens)
25. Select Case Tokens(i)
26. Case "("
27. Push oprStack, Tokens(i)
28. Case ")"
29. If oprStack.Count > 0 Then
30. Do While (oprStack.Count > 0 And
Peek(oprStack) <> "(")
31. Push rpnStack, Pop(oprStack)
32. Loop
33. If oprStack.Count > 0 Then
34. Pop oprStack
35. End If

63. End If
64. Case Else
65. Push rpnStack, Tokens(i)
66. End Select
67. tmpOp = ""
13
68. Next i
69.
70. Do While oprStack.Count > 0
71. Push rpnStack, Pop(oprStack)
72. Loop
73.
74. '##### Tinh toan #####
75.
76. On Error Resume Next
77.
78. Dim ResultStack As New Collection
79.
80. Dim j As Integer
81. For j = 1 To rpnStack.Count
82. Dim a As Double, b As Double
83. Select Case rpnStack.Item(j)
84. Case "u+"
85. Case "u-"
86. Push ResultStack, CStr(-Val(Pop(ResultStack)))
87. Case "^"
88. b = Val(Pop(ResultStack))
89. a = Val(Pop(ResultStack))
90. Push ResultStack, CStr(a ^ b)
91. Case "*"

121. ' Ba hàm cần thiết để dùng Collection thay cho ngăn xếp
122. Private Sub Push(ByRef c As Collection, ByVal value As String)
123. c.Add value
124. End Sub
125.
15
126. Private Function Pop(ByRef c As Collection) As String
127. Pop = c.Item(c.Count)
128. c.Remove c.Count
129. End Function
130.
131. Private Function Peek(ByVal c As Collection) As String
132. Peek = c.Item(c.Count)
133. End Function
Lưu ý
Do Collection sử dụng kiểu dữ liệu Variant (có kích thước 16 byte) nên sẽ cần nhiều bộ nhớ hơn
các kiểu dữ liệu khác. Tác giả bài viết không khuyên dùng trong chương trình này.
16