資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚
法律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
更新時間: 30-7-2019
367 次瀏覽
廣告