drzewo analizy wyrażenia algorytm

0

Witam, mam problem ze znalezieniem informacji i pomocy naukowych do zadania:

Dane jest drzewo analizy wyrażenia, napisz algorytm, który poprawnie wypisze wyrażenie zakodowane w drzewie, uwzględniając kolejność i priorytet działań. Każdemu operatorowi powinna towarzyszyć jedna para nawiasów. (drzewo w załączniku)

Przeszukałem Cormena ale nie mogę nic znaleźć. Czy to jest drzewo AST? nie mam pojęcia czego szukać i gdzie, proszę o pomoc.

1

(((a+b)*(c*d))+e)*f

0

no już mi to lekko rozjaśniłeś, a jak nazywa się to zagadnienie?

i jeszcze jest drugi podpunkt tego zadania:

Dane jest drzewo analizy wyrażenia, napisz algorytm, który wypisze wyrażenie zakodowane w drzewie,* stosując się do zasad Odwrotnej Notacji Polskiej.*

z góry dzięki za odpowiedź.

0

czy będzie to wyglądać tak:

a b + c d ** e + f *

0

tak

0

A jak ugryźć algorytm, jak oznaczyć węzeł a jak liść (czy może całkiem inne podejście )? Jak należy rozpatrywać to drzewo od góry do dołu czy odwrotnie?

Prosiłbym o jakiś mały przykładowy fragment pseudokodu :)

1
#include <iomanip>
#include <iostream>
#include <string>
using namespace std;

struct node
  {
   string data;
   node *left,*right;
   node(const string &data,node *left=0,node *right=0):data(data),left(left),right(right) {}
  };

void show(node *n,int p=1)
  {
   if(n->left) show(n->left,p+1);
   cout<<setw(3*p)<<' '<<n->data<<endl;
   if(n->right) show(n->right,p+1);
  }

void onp(node *n)
  {
   if(n->left) onp(n->left);
   if(n->right) onp(n->right);
   cout<<n->data<<' ';
  }

void opr(node *n)
  {
   if(n->left) { cout<<"( "; opr(n->left); }
   cout<<' '<<n->data<<' ';
   if(n->right) { opr(n->right); cout<<" )"; }
  }

int main()
  {
   node *tree=new node
     (
      "*",
      new node
        (
         "+",
         new node
           (
           	"*",
           	new node
           	  (
           	   "+",
           	   new node("a"),
           	   new node("b")
           	  ),
           	new node
           	  (
           	   "*",
           	   new node("c"),
           	   new node("d")
           	  )
           ),
         new node("e")
        ),
      new node("f")
     );
   show(tree);
   onp(tree); cout<<endl;
   opr(tree); cout<<endl;
   return 0;
  }
1

Dużo w zrozumieniu tematu może pomóc:
http://edu.i-lo.tarnow.pl/inf/alg/001_search/0118.php

1 użytkowników online, w tym zalogowanych: 0, gości: 1