표현식 트리 알고리즘을 구현하는 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