Thuật toán tính giá trị biểu thức

Phương pháp nghịch đảo Balan hoặc cây biểu thức sẽ làm cho các bạn mới học lúng túng. Đây là một phương cực kỳ đơn giản các bạn có thể đọc hiểu và vận dụng được Biểu thức đơn giản bao gồm 2 phép toán + và * Vd: 2*5+3+4*3+2 Cách tính:

Nội dung chính Show

Giới thiệu
Nội dung cập nhật
Các phương thức chung
Chuyển đổi từ biểu thức infix sang postfix
Tính giá trị của biểu thức postfix
Chuyển biểu thức infix thành cây biểu thức
Video liên quan

Nếu trong biểu thức có phép + thì lấy phần biểu thức đầu + phần biểu thức cuối Ngược lại nếu trong biểu thức có phép * thì lấy phần đầu biểu thức * phần cuối biểu thức

Ngược lại biểu thức = chính số đó

Minh họa: “2*5+3+4*3+2” = “2*5″+”3+4*3+2” = 2*5+3+”4*3+2″= 2*5+3+”4*3″+2 = 2*5+3+4*3+2 Biểu thức bao gồm các phép toán +, -, * Trước khi tính biểu thức ta thêm vào dấu + trước mỗi dấu – (nếu có dấu – đứng đầu câu thì để nguyên) Tính toán bình thường như không có phép – Biểu thức bao gồm phép toán +, -, *, / Thêm + vào trước – Thêm * vào trước /

Trong lúc đổi xâu thành số nếu có lỗi thì cắt bỏ ký tự đầu của xâu -> tiếp tục đổi xâu thành số và sau đó lấy nghịch đảo. Tiến hành tính toán bình thường như biểu thức chỉ có + và *

Nếu bạn sử dụng giải thuật này trong bài viết bạn, làm ơn ghi rõ tên tác giả của giải thuật qvluom

Code minh họa với 4 phép toán +, -, *, /

#include #include #include #include #include #include using namespace std; int check_to_number(string s) //kiem tra la so { int check = 1, l = s.length(); for (int i = 1; i 0) { if (check == 1) //neu la so binhf thuong { stringstream ss (s); ss >> number; } if (check > 1) { stringstream ss (s.substr(1,s.length()-1)); ss >> number; if (check == 2) number = 0 - number; //neu la phep tru if (check == 3) number = 1/number; // neu la phep chia } return number; } } float process(string s, int l, int r) { int li = 0, ri = r; if (check_to_number(s)) return convert_to_number(s); //{ cout <<" "<

Trong một số bài viết trước đây tôi đã giới thiệu thuật toán chuyển đối biểu thức toán học giữa các dạng trung tố (infix), tiền tố (prefix) và hậu tố (postfix). Đồng thời tôi cũng trình bày phương pháp tính giá trị của các biểu thức này cũng như xây dựng cây biểu thức trực quan qua chương trình Y2 – Expression Converter Demo. Tuy nhiên thuật toán này chỉ mới hỗ trợ các toán tử hai ngôi (binary operation), trong bài viết này tôi sẽ mở rộng để thuật toán làm việc với các toán tử một ngôi (unary operation).

Cập nhật (23 March 2011):

Cảm ơn bạn ngngthanhmai đã góp ý về một số trường hợp lỗi với toán tử “-” (unary).

Giới thiệu

Do thời gian có hạn nên tôi chỉ minh họa với hai toán tử là “-“ (số âm) và “sqrt()” (căn bậc hai). Hai toán tử /hàm này có điểm chung là đứng trước toán hạng. Các toán tử đứng sau toán hạng như “!” (giai thừa) cũng có cơ chế xử lý tương tự.

Đối với các toán tử (hoặc hàm) như sqrt, sin, cos,… có hai cách viết là đặt các toán hạng bên trong dấu ngoặc đơn hoặc không (ví dụ: sqrt(x) hoặc sqrt x). Ở đây tôi chọn cách đầu tiên để có thể đặt một biểu thức vào trong cặp ngoặc đơn và làm biểu thức rõ ràng hơn.

Nội dung cập nhật

Các cập nhật sau nằm trong thư viện Y2ExprConverter.dll thuộc chương trình Y2-ExpressionConverter (version 1.2). Tôi chỉ sửa đổi một vài phương thức chuyển đổi và tính toán với postfix, tạo cây biểu thức từ infix. Các phương thức còn lại bạn có thể thực hiện tương tự. Tất cả các sửa đổi này đều được cập nhật đầy đủ mã nguồn và chức năng cho chương trình Y2-ExpressionConverter (version 1.2).

Các phương thức chung

Sửa đổi phương thức định dạng biểu thức để xử lý các trường hợp nhập nhiều toán tử liền nhau (chỉ cho phép hai toán tử với toán tử thứ hai là “-“):

public static string FormatExpression(string expression) { expression = expression.Replace(" ", ""); expression = Regex.Replace(expression, @"(\+|\-|\*|\/|\%){3,}", match => match.Value[0].ToString()); expression = Regex.Replace(expression, @"(\+|\-|\*|\/|\%)(\+|\*|\/|\%)", match => match.Value[0].ToString() ); expression = Regex.Replace(expression, @"\+|\-|\*|\/|\%|\)|\(", match => String.Format(" {0} ", match.Value) ); expression = expression.Replace(" ", " "); expression = expression.Trim(); return expression; }

Sửa đổi phương thức lấy độ ưu tiên và kiểm tra toán tử (bổ sung toán tử sqrt):

public static int GetPriority(string op) { if (op == "sqrt") return 3; if (op == "*" || op == "/" || op == "%") return 2; if (op == "+" || op == "-") return 1; return 0; } public static bool IsOperator(string str) { return Regex.Match(str, @"^(\+|\-|\*|\/|\%|sqrt)$").Success; }

Chuyển đổi từ biểu thức infix sang postfix

– Khi gặp toán tử dấu âm “-“ (toán tử “-“ đứng liền sau toán tử khác), ta nối toán tử này với toán hạng ngay sau nó

– Khi gặp toán tử “sqrt” ta push vào stack

public static string Infix2Postfix(string infix) { infix = FormatExpression(infix); string[] tokens = infix.Split(' ').ToArray(); Stack stack = new Stack(); StringBuilder postfix = new StringBuilder(); for (int i = 0; i < tokens.Length; i++) { string token = tokens[i]; if (IsOperator(token)) { if ((i==0) || (i > 0 && (IsOperator(tokens[i - 1]) || tokens[i - 1]=="(" ))) { if (token == "-") { postfix.Append(token + tokens[i + 1]).Append(" "); i++; } else if (token == "sqrt") { stack.Push(token); } } else { while (stack.Count > 0 && GetPriority(token) <= GetPriority(stack.Peek())) postfix.Append(stack.Pop()).Append(" "); stack.Push(token); } } else if (token == "(") stack.Push(token); else if (token == ")") { string x = stack.Pop(); while (x != "(") { postfix.Append(x).Append(" "); x = stack.Pop(); } } else// (IsOperand(s)) { postfix.Append(token).Append(" "); } } while (stack.Count > 0) postfix.Append(stack.Pop()).Append(" "); return postfix.ToString(); }

Tính giá trị của biểu thức postfix

Ta chỉ lấy một toán hạng ra khỏi stack để tính thay vì hai toán hạng như đối với các toán tử binary

public static double EvaluatePostfix(string postfix) { Stack stack = new Stack(); postfix = postfix.Trim(); IEnumerable enumer = postfix.Split(' '); foreach (string s in enumer) { if (IsOperator(s)) { double x = stack.Pop(); if (s == "sqrt") { x = Math.Sqrt(x); stack.Push(x); } else { double y = stack.Pop(); switch (s) { case "+": y += x; break; case "-": y -= x; break; case "*": y *= x; break; case "/": y /= x; break; case "%": y %= x; break; } stack.Push(y); } } else // IsOperand { stack.Push(double.Parse(s)); } } return stack.Pop(); }

Chuyển biểu thức infix thành cây biểu thức

private static void CreateSubTree(Stack opStack, Stack nodeStack) { BinaryTreeNode node = opStack.Pop(); node.RightChild = nodeStack.Pop(); if(node.Value!="sqrt") node.LeftChild = nodeStack.Pop(); nodeStack.Push(node); } public static BinaryTreeNode Infix2ExpressionTree(string infixExpression) { List prefix = new List(); Stack operatorStack = new Stack(); Stack nodeStack = new Stack(); infixExpression = FormatExpression(infixExpression); string[] tokens = infixExpression.Split(' ').ToArray(); for (int i = 0; i < tokens.Count(); i++) { if (IsOperator(tokens[i])) { if (i > 0 && IsOperator(tokens[i - 1])) { if (tokens[i] == "-") { nodeStack.Push(new BinaryTreeNode(tokens[i] + tokens[i + 1])); i++; } else if(tokens[i]=="sqrt") operatorStack.Push(new BinaryTreeNode(tokens[i])); } else { while (operatorStack.Count > 0 && GetPriority(operatorStack.Peek().Value) >= GetPriority(tokens[i])) CreateSubTree(operatorStack, nodeStack); operatorStack.Push(new BinaryTreeNode(tokens[i])); } } else if (tokens[i] == "(") operatorStack.Push(new BinaryTreeNode(tokens[i])); else if (tokens[i] == ")") { while (operatorStack.Peek().Value != "(") CreateSubTree(operatorStack, nodeStack); operatorStack.Pop(); } else //if (IsOperand(tokens[i])) nodeStack.Push(new BinaryTreeNode(tokens[i])); } while (operatorStack.Count > 0) CreateSubTree(operatorStack, nodeStack); return nodeStack.Peek(); }

Các đoạn mã nguồn trên được trích từ tập tin Y2Expression.cs trong thư viện Y2ExprConverter.dll. Bạn có thể xem mã nguồn hoàn chỉnh của tập tin này tại link sau:

C# – Y2Expression: Convertion, Evaluation and Build Expression Tree

https://yinyangit.wordpress.com

Cryto Giá

Thuật toán tính giá trị biểu thức

Giới thiệu

Nội dung cập nhật

Các phương thức chung

Chuyển đổi từ biểu thức infix sang postfix

Tính giá trị của biểu thức postfix

Chuyển biểu thức infix thành cây biểu thức

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội