簡單算術運算式二叉樹的構建和求值 (資料結構)

簡單算術運算式二叉樹的構建和求值 (資料結構)

題目要求

先用二叉樹來表示一個簡單算術運算式，樹的每一個結點包括一個運算子或運算元，在簡單算術運算式中只包含 加 減 乘 除 和一位正整數且格式正確（不包括括號），并且要按照先乘除后加減的原則構造二叉樹，下圖所示為 “1+2*3-4/5” 代數運算式對應的二叉樹，然后由對應的二叉樹計算該運算式的值，

先用二叉樹來表示一個簡單算術運算式，樹的每一個結點包括一個運算子或運算元，
在簡單算術運算式中只包含 + - * / 和一位正整數且格式正確（不包括括號），
并且要按照先乘除后加減的原則構造二叉樹，下圖所示為 “1+2*3-4/5” 代數運算式對應的二叉樹，
然后由對應的二叉樹計算該運算式的值，

思考程序

	按照題目所述, 自己根據一個更復雜更全面的運算式(出現了所有的情況)，畫多一個圖，尋找規律，
	
	運算式的要求:
		(1)要出現 + - * / 中所有的符號
		(2)各優先級符號要出現不同的次數來相互搭配
		
	如：1+2+3*4*5+6+7+8/2*9+9

我大意了，在作圖的時候忘記用減號 - 了，但在這里沒有影響

二叉樹的特點

1. 數字只能是葉子節點, 且葉子節點只能是數字
2. + - 符號永遠只能祖宗節點或者左孩子節點
3. 如果遇到 * / 則 將其作為祖宗節點來看, 其右孩子節點只能是 數字, 左孩子節點是 * / 符號或者 數字

思路分析

1. 遍歷字串，利用堆疊存盤節點：
        p = new BTNode;
        p->lchild = NULL;
        p->rchild = NULL;
	
	(1) 遇到數字：
		思路：
		若分情況討論情況：
			1. 堆疊為空，即這是字串第一個數字
			2. 左右邊可能為 + - * / 其中之一，
			3. 而如果是乘除，則要先進行乘除運算
			可見，如果對數字進行分情況處理，將會十分復雜，
				不妨考慮直接將其壓堆疊，
				在遇到運算子在進行符號的優先級進行討論，
		
		代碼操作：p->elem = ch;  sta.push(p);
			
    (2) 遇到乘除:
        思路：將 * (或/) 作為父節點，
        	左節點為堆疊頂元素 num1 或者 * (或/)，
        	右節點為字串下一個元素num2
        
        代碼操作：新建節點 p 賦值 * (或/)，
        		新建節點 r 賦值 字串下一個元素num2，
        		彈出堆疊頂元素作為節點l, 
        		然后連接：p->lchild = l, p->rchild = r;
			
			p->elem = ch;
            BTNode *r = new BTNode;
            i++;
            r->elem = str[i];
            r->lchild = NULL;
            r->rchild = NULL;
            p->rchild = r;
            p->lchild = sta.top();
            sta.pop();
            sta.push(p);
			
	(3) 遇到加減: 
        思路：通過觀察二叉樹中，父節點的左右孩子節點的各種可能找出規律
        	兩種情況: [1]堆疊內元素個數為2，
        			則堆疊頂元素必為 * 或 / ，
        			則將其作為當前節點右的孩子節點，
        			然后弾堆疊，剩下元素處理程序與 [2] 一致
        			 [2]堆疊內元素個數為1，
        			 則堆疊內元素必為 +、-、數字(首數字)其中之一,
        			 則將其作為當前節點的左孩子節點即可，
        			 然后弾堆疊，將當前節點壓堆疊
        			 
        代碼操作：
           p->elem = ch;
            if(sta.size() == 2) {
                BTNode *r = sta.top();
                sta.pop();
                sta.top()->rchild = r;
            }
            p->lchild = sta.top();
            sta.pop();
            sta.push(p);
            
2. 遍歷字串完成后，觀察到有幾種情況
	(1)只有 + (或-)操作, 則堆疊內有兩個元素，
		堆疊底元素是數字，堆疊頂元素是運算子，
	(2)只有 * 或(/)操作，則堆疊內只有一個運算子，
	(3)既有 + (或-)操作也有 * 或(/)操作，則堆疊內有兩個元素，
		堆疊底元素是 * (或/)或數字，堆疊頂元素是運算子，
	
	所以可以看成(2)是一種情況，(1)(3)是另一種情況
	
	代碼操作：
		if (sta.size() == 2) {
            BTNode *r = sta.top();
            sta.pop();
            sta.top()->rchild = r;
        }
        BT = sta.top();

代碼實作

#include <iostream>
#include <string>
#include <cstring>
#include <stack>
using namespace std;

#define ElemType char

typedef struct node {
    ElemType elem;
    struct node *lchild;
    struct node *rchild;
}BTNode;

void createBT(BTNode* &BT, string str) {
    stack<BTNode*> sta;
    BTNode *p;
    for(int i = 0; i < str.size(); i++) {
        p = new BTNode;
        p->lchild = NULL;
        p->rchild = NULL;
        char ch = str[i];
        if(ch == '*' || ch == '/') {
            p->elem = ch;
            BTNode *r = new BTNode;
            i++;
            r->elem = str[i];
            r->lchild = NULL;
            r->rchild = NULL;
            p->rchild = r;
            p->lchild = sta.top();
            sta.pop();
            sta.push(p);
        } else if(ch == '+' || ch == '-') {
            p->elem = ch;
            if(sta.size() == 2) {
                BTNode *r = sta.top();
                sta.pop();
                sta.top()->rchild = r;
            }
            p->lchild = sta.top();
            sta.pop();
            sta.push(p);
        } else {
            p->elem = ch;
            sta.push(p);
        }
        p = NULL;
        free(p);
    }

    if (sta.size() == 2) {
        BTNode *r = sta.top();
        sta.pop();
        sta.top()->rchild = r;
    }
    BT = sta.top();
}

int calculate(BTNode* &BT) {
    char ch = BT->elem;
    if(ch == '+') return calculate(BT->lchild) + calculate(BT->rchild);
    else if(ch == '-') return calculate(BT->lchild) - calculate(BT->rchild);
    else if(ch == '*') return calculate(BT->lchild) * calculate(BT->rchild);
    else if(ch == '/') return calculate(BT->lchild) / calculate(BT->rchild);
    else return ch - '0';
}

void displayBT(BTNode* &BT) {
    if(BT != NULL){
		cout << BT->elem;
		displayBT(BT->lchild);
		displayBT(BT->rchild);
	}
	else{
		printf("#");
	}
}

void destroyBT(BTNode* &root) {
    if(root != NULL) {
        destroyBT(root->lchild);
        destroyBT(root->rchild);
        free(root);
    }
}

int main() {
    string str = "1+2+3*4*5+6+7+8/2*9+9";
    BTNode *BT;

    createBT(BT, str);
    cout << "簡單算術運算式二叉樹為：\n";
    displayBT(BT);

    cout << "\n\n該運算式的運算結果為：" << calculate(BT) << "\n\n";

    destroyBT(BT);

    system("pause");
    return 0;
}

運算結果

總結

	知識點：根據算術運算子的優先級進行分類討論，運用了堆疊這一資料結構，
	
	拓展思考：上述代碼先把 * (或/) 的運算進行操作，
			而 + (或-) 則先存在堆疊里，不難發現，
			可以不通過構建二叉樹，利用堆疊來運算簡單的運算式，
	
	拓展知識：
		題目所給這一類運算式叫中綴運算式，
		 指運算子是以中綴形式處于運算元的中間，
		 這一類運算式是人們常用的算術表示方法，
		 但通過這道題可以發現，中綴運算式不容易被計算機決議，
		 要使用還要經過處理(利用堆疊)，
		而前綴運算式(波蘭式，波蘭數學家Jan Lukasiewicz)
		 與后綴運算式(逆波蘭式, RPN)，則更容易被計算機進行識別運算，