Cây Biểu thức_ Lập trình C++

**) Đối tượng hướng đến:

các bạn đã và đang học cấu trúc dữ liệu và giải thuật, các bạn chưa học muốn tìm hiểu trước thì vui lòng tìm hiểu về stack, cây nhị phân,...để dễ dàng tiếp thu thêm kiến thức này

**) Nội dung



    Cây Biểu thức là cây nhị phân trong đó các node lá là các toán hạng (a,b,c,..A,B,C,...) và các nút cha là các toán tử (+,-,*,/,...) thỏa mãn độ ưu tiên toán tử (nhân chia trước công trừ sau). Việc cài đặt  một cây nhị phân tìm kiếm thì có vẻ đơn giản nhưng để cài đặt một cây biểu thức thì không phải dễ đâu nhé 😅😅😅😅😅😅😅😅😅😅😅, bản thân mình phải trải qua một thời gian khá dài (khoảng 2 tiếng, 😅😅😅😅😅😅😅😅😅😅😅 ) từ bạn bè mới cài được nó. Đùa tý thôi, thật ra cũng khá khó thôi, không đến nỗi. Rồi, Dưới đây là hình ảnh của cây biểu thức





  để cài đặt được một cái cây "ngắn ngắn " thế này cũng tốn khá nhiều thời gian đây, mình sẽ sơ lược các bước để cài đặt cây, code mẫu thì các bạn kéo xuống dưới để xem nhé!!!




**) Các bước cài đặt cây biểu thức


Bước 1: chuyển biểu thức đã cho sang dạng hậu tố, ví dụ: (a+b)*c  -->ab+c*, (a*c-b)*d->ac*b-d*,...(các bạn  nào chưa biết thì chịu khó search google hậu tố là gì nhá)
  - dùng 1 stack chứa các phần tử toán tử như cộng trừ nhân chia nha, stack này ban đầu được khởi tạo rỗng, sau đó trong quá trình duyệt biểu thức thì nếu gặp toán tử thì mới thêm vào, stack thì có thể khai báo thư viện stack hoặc tự cài cũng được, ở đây mình dùng thư viện cho nhanh(không khuyến khích).

  -tạo một biến string result; rỗng ruột, trong quá trình duyệt biểu thức, gặp toán hạng thì thêm vào biến string này, toán hạng là các biến a,b,c,d,..A,..Z nha.

- Và đây là một số quy tắc lúc duyệt đọc kỹ nha:
  +)nếu gặp dấu '(' thì cho vào stack
  +)nếu gặp toán hạng thì cho vào biến result(thêm vào biến result)
  +)nếu gặp toán tử thì xuất lần lượt các toán tử có độ ưu tiên cao  hơn đang nằm trên stack qua biến result, rồi lại thêm toán tử đó vào stack(đọc code bên dưới để biết thêm).
  +) nếu gặp dấu ')' thì lấy lần lượt các phần từ từ stack qua biến result cho đến khi gặp ký tự '(', lưu ý rằng ký tự '(' sẽ không được thêm vào result nhưng trong quá trình vận chuyển các phần tử từ stack qua result thì nếu gặp ký tự này thì dừng, và "tháo" nó ra khỏi stack luôn.
  +) cuối cùng, khi xét hết biểu thức rồi, thì trên stack còn bao nhiêu ký tự, đem hết xuống result.
  +) cuối cuối cùng, kaka, return về biến result nha.


==>đến đây ta được một chuỗi result biểu diễn biểu thức dạng postfix, nhưng chưa xong, chúng ta đang tạo cây mà.

thế thì phải tạo một câu trúc Node, và Cây nhị phân (bạn nào học đến đây rồi thì khuyến khích đọc tiếp, bạn nào chưa học đến cây nhị phân thì đọc đến đây là đủ rồi, về học tiếp phần cây nhị phân rồi quay lại đọc tiếp nha).

Từ chuỗi đã thu được ta lại dùng thêm stack<Node*> để chứa các Node, những cái Node này chứa ký tự kiểu char.
khi duyệt biểu thức vừa thu được bên trên , nếu gặp toán hạng thì tạo Node và cho vào stack, nếu gặp toán tử thì tạo Node chứa toán tử đó, sau đó gán cho Right của Node đó =stack.top()(tức là phần tử dầu tiên của stack), sau đó xóa phần tử đầu của stack đó luôn, tiếp theo gán cho Left của Node đó =stack.top()(top bây giờ khác top lúc nãy rồi nha), rồi cũng xóa top của stack một lần nữa, và cuối cùng là gán top của stack bằng cái Node vừa tạo, làm tương tự cho đến khi duyệt hết biểu thức.


Vẫn chưa xong, khi duyệt hết biểu thức, nếu các phép toán đúng thì chắc chắn cái stack của bạn chỉ còn chứa một phần tử, Nó chính là cái gốc của cây cần tìm. rồi đến dây thì dễ rồi, các bạn duyệt cây để xem kết quả thôi.


Còn đây là code mẫu của mình, nếu có thắc mắc thì comment bên dưới nha.

#include<iostream>
#include<stack>
using namespace std;
bool isOperator(char x)
{
 return x == '+' || x == '-' || x == '*' || x == '/';
}
int getPriority(char x)
{
 if (x == '+' || x == '-') return 1;
 if (x == '*' || x == '/') return 2;
 return 0;
}
bool isOperand(char x)
{
 if ((x > 64 && x<91) || (x>96 && x < 123)) return true;
 return false;
}
string toPostfix(string &A)
{
 stack<char> opStack;       //stack dùng để chứa các toán tử ( ) + - * /
 string result = "";        //tạo một chuỗi trống, chuỗi này sẽ là chuỗi được trả về
 for (int i = 0; i < A.size(); i++)
 {
  if (A[i]=='(')   //nếu là dấu mở ngoặc thì thêm vào stack 
  {
   opStack.push(A[i]);
  }
  else
  {
   if (isOperand(A[i]))   //nếu là toán hạng a, b,c,d,e,f... thì thêm vào chuỗi result
   {
    result += A[i];
   }
   else
   {
    if (isOperator(A[i]))  //nếu là toán tử thì đưa hết những toán tử có độ ưu tiên cao hơn A[i] vào result, rồi thêm A[i]vào stack 
    {
     while (!opStack.empty() && getPriority(opStack.top()) >= getPriority(A[i]))
     {
      result += opStack.top();
      opStack.pop();
     }
     opStack.push(A[i]);
    }
    else
    {
     if (A[i] == ')')
     {
      while (!opStack.empty() && opStack.top() != '(')
      {
       result += opStack.top();
       opStack.pop();
      }
      opStack.pop();
     }
    }
   }
  }
 }
 while (!opStack.empty())   //trong stack còn bao nhiêu thì cứ thêm vào
 {
  result += opStack.top();
  opStack.pop();
 }
 return result; 
}
//đến đây xử lý được xong chuỗi, tức là đưa chuỗi về dạng hậu tố, sau đây ta sẽ đưa chúng vào cây
struct Node
{
 char data;
 Node*Left;
 Node*Right;
 Node()
 {
  this->Left = this->Right = NULL;
 }
};
struct ExpressionTree
{
 Node* Root;          //cây nhị phân này chỉ cần nắm bắt nút gốc, các nút còn lại thì dựa vào nút gốc
 ExpressionTree()
 {
  this->Root = NULL;
 }
};
void showInfix(Node*&R)
{
 if (R)
 {
  showInfix(R->Left);
  cout << R->data;
  showInfix(R->Right);
 }
}
void showPostfix(Node*&R)
{
 if (R)
 {
  showPostfix(R->Left);
  showPostfix(R->Right);
  cout << R->data;
 }
}
void showPrefix(Node*&R)
{
 if (R)
 {
  cout << R->data;
  showPrefix(R->Left);
  showPrefix(R->Right);
 }
}
void addToExpression(Node*&R, string str)
{
 str = toPostfix(str);
 stack<Node*> stackNode;
 for (int i = 0; i < str.size(); i++)
 {
  if (isOperand(str[i]))
  {
   Node*P = new Node;
   P->data = str[i];
   stackNode.push(P);
  }
  else
  {
   if (isOperator(str[i]))
   {
    Node*P = new Node;
    P->data = str[i];
    P->Right = stackNode.top();
    stackNode.pop();
    P->Left = stackNode.top();
    stackNode.pop();
    stackNode.push(P);
   }
  }
 }
 R = stackNode.top();
}
int main()
{
 ExpressionTree ET;
 string str;
 cout << "enter expression, enter '#' to exit:\n";
 char a = 'h';
 while (a != '#') 
 {
  cin >> a;
  if (a != '#') str += a;
 }
 addToExpression(ET.Root, str);
 cout << "\nPreFix: \n";
 showPrefix(ET.Root);
 cout << "\nPostFix: \n";
 showPostfix(ET.Root);
 cout << "\nInFix: \n";
 showInfix(ET.Root);
 return 0;
}

                                                                                                                              Thân!
                                                                                                                               Tạ Tạ