ต้นไม้นิพจน์ (Expression Tree) คือต้นไม้ทวิภาคพื้นฐานที่ใช้แทนนิพจน์ ในต้นไม้นิพจน์ โหนดภายในจะสอดคล้องกับตัวดำเนินการ (operators) และโหนดใบแต่ละโหนดจะสอดคล้องกับตัวถูกดำเนินการ (operands) นี่คือโปรแกรม C++ สำหรับการนำอัลกอริทึมต้นไม้นิพจน์มาใช้งาน ซึ่งรับนิพจน์แบบ postfix เป็นอินพุตและสร้างต้นไม้นิพจน์ที่สอดคล้องกันซึ่งถูกเดินทางแบบ inorder
อัลกอริทึม
Begin ฟังก์ชัน construct_expression_tree(): Flag = 1 เมื่อเป็นตัวถูกดำเนินการ Flag = -1 เมื่อเป็นตัวดำเนินการ S = suffix[0] หมายถึงอ่านตัวถูกดำเนินการตัวแรกจากนิพจน์ สำหรับ i = 0 และจนกว่า s != 0 ตรวจสอบสัญลักษณ์ว่าเป็นตัวถูกดำเนินการหรือตัวดำเนินการ เรียกฟังก์ชัน void inorder() สำหรับการเดินทางแบบ inorder พิมพ์ผลลัพธ์ เพิ่ม i จบ
ตัวอย่างโค้ด
#include <iostream> using namespace std; struct n//node declaration { char d; n *l; n *r; }; char pf[50]; int top = -1; n *a[50]; int r(char inputch)//check the symbol whether it is an operator or an operand. { if (inputch == '+' || inputch == '-' || inputch == '*' || inputch == '/') return (-1); else if (inputch >= 'A' || inputch <= 'Z') return (1); else if (inputch >= 'a' || inputch <= 'z') return (1); else return (-100); } void push(n *tree)//push elements in stack { top++; a[top] = tree; } n *pop() { top--; return (a[top + 1]); } void construct_expression_tree(char *suffix) { char s; n *newl, *p1, *p2; int flag; s = suffix[0]; for (int i = 1; s!= 0; i++) { flag = r(s); if (flag == 1) { newl = new n; newl->d = s; newl->l = NULL; newl->r = NULL; push(newl); } else { p1 = pop(); p2 = pop(); newl = new n; newl->d = s; newl->l = p2; newl->r = p1; push(newl); } s = suffix[i]; } } void inOrder(n *tree)//perform inorder traversal { if (tree != NULL) { inOrder(tree->l); cout << tree->d; inOrder(tree->r); } } int main(int argc, char **argv) { cout << "Enter Postfix Expression : "; cin >>pf; construct_expression_tree(pf); cout << "\nInfix Expression : "; inOrder(a[0]); return 0; }
ผลลัพธ์
Enter Postfix Expression : 762*+6+ Infix Expression : 7+6*2+6
