#include<stdlib.h> #include<stdio.h> #include<string.h> #include<ctype.h> #define MAX_LEN 5 typedef struct node { char optr; int data; struct node* lchild; struct node* rchild; }BTNode; BTNode* getNode(char* str, int& pos) { BTNode* createTree(char* str, int& pos); BTNode* p = new BTNode; char ch = str[0]; if (isdigit(ch)) { int i = 0; char data[MAX_LEN]; while (isdigit(ch = str[i])) data[i++] = ch; p->data = atoi(data); pos += i; } else if (ch == ‘+’ || ch == ‘-’ || ch == ‘’ || ch == ‘/’) { p->optr = ch; pos += 1; p = createTree(str + 1, pos); } else if (ch == ‘)’) { pos += 1; return NULL; } else if (ch == ‘\0’) return NULL; return p; } int getPriority(char optr) { switch (optr) { case’+’: case’-’: return 1; case’’: case’/’: return 2; } return 0; } BTNode* createTree(char* str, int& pos) { int pos1 = 0; BTNode* lchild = getNode(str + pos1, pos1); BTNode* root = getNode(str + pos1, pos1); BTNode* rchild = getNode(str + pos1, pos1); root->lchild = lchild; root->rchild = rchild; BTNode* node; while ((node = getNode(str + pos1, pos1))) { if (getPriority(root->optr) > getPriority(node->optr)) { node->lchild = root; node->rchild = getNode(str + pos1, pos1); root = node; } else { node->lchild = root->rchild; root->rchild = node; node->rchild = getNode(str + pos1, pos1); } } pos += pos1; return root; } int result(BTNode* b) { int n1, n2; switch (b->optr) { case’+’: n1 = result(b->lchild); n2 = result(b->rchild); b->data = n1 + n2; break; case’-’: n1 = result(b->lchild); n2 = result(b->rchild); b->data = n1 - n2; break; case’*’: n1 = result(b->lchild); n2 = result(b->rchild); b->data = n1 * n2; break; case’/’: n1 = result(b->lchild); n2 = result(b->rchild); b->data = n1 / n2; break; default: return b->data; } return b->data; }
int main() { BTNode* b = NULL, * q = NULL; char str[100]; printf(“请输入符合要求的代数表达式:”); scanf("%s", str); int n = 0, i = 0; while (str[i++] != ‘\0’) n++; int pos = 0; b = createTree(str, pos); printf(“该表达式的值为:%d\n”, result(b)); }
|