C++ 实施表达式树算法的程序
表达式树基本上是一种二叉树,用于表示表达式。在表达式树中,内部节点对应于运算符,而每个叶节点对应于一个操作数。以下是一个 C++ 程序,用于实现表达式树算法,它以后缀表达式作为输入,并生成中序遍历的相应表达式树。
算法
Begin function construct_expression_tree(): Flag = 1 when it is operand. Flag = -1 when it is operator. S = suffix[0] means read the first operand from the expression. For i = 0 and until s != 0 Check symbol is operand or operator. Call function void inorder() for inorder traversal. Print the results. Increment i End.
示例代码
#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
广告