فرض کنید عبارت زیر را دارید :

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

عبارت بالا یک عبارت infix (میان ترتیب) است زیرا عملگر بین عملوند هایش آمده است ، به طور مثال در عبارت بالا ” – ” بین c و d آمده است.

در این پست عباراتی را که بررسی می کنیم شامل عملگرهای + , – , / , * و پرانتز است. اولویت این عملگرها به ترتیب زیر است:

1. * ، /
2. – ، +

و این عملگرها شرکت پذیری از سمت چپ به راست دارند.

درخت عبارت بالا به شکل زیر می شود:

اگر عبارت بالا را به صورت inorder پیمایش کنیم یعنی ابتدا ریشه را ببینیم بعد فرزند چپ و بعد فرزند راست، دقیقا عبارت بالا بدون پرانتز به دست می آید که همان شکل infix است:

In-order:
1-Traverse the left subtree by recursively calling the in-order function
2-Display the data part of root element (or current element)
3-Traverse the right subtree by recursively calling the in-order function

inorder(node)
  if node == null then return
  inorder(node.left)
  visit(node)
  inorder(node.right)

a + b * c – d / e – f

prefix (پیش ترتیب) یک عبارت محاسباتی یعنی عملگر قبل از عملوند هایش بیاید،برای اینکه شکل prefix عبارت بالا را به دست بیاوریم باید درخت بالا به صورت preorder پیمایش کنیم یعنی ابتدا ریشه را ببینیم بعد فرزند چپ و بعد فرزند راست که عبارت زیر به دست می آید:

Pre-order:
1-Display the data part of root element (or current element)
2-Traverse the left subtree by recursively calling the pre-order function.
3-Traverse the right subtree by recursively calling the pre-order function.

preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left) 
  preorder(node.right)

/ * + a b – c d – e f

postfix (پس ترتیب) یک عبارت محاسباتی یعنی عملگر بعد از عملوندهایش بیاید، که می توان شکل postfix یک عبارت محاسباتی را از روی درختش با استفاده از پیمایش postorder با کمی تغییر به دست آورد.
در پیمایش postorder ابتدا فرزند چپ و بعد فرزند راست و بعد ریشه را می بینیم ولی باید در این الگوریتم کمی تغییر ایجاد کنیم، و آن این است که به جای اینکه ابتدا فززند چپ و بعد راست و بعد ریشه را ببینیم ، ایتدا فرزند راست و بعد فرزند چپ و بعد ریشه را ببینیم که عبارت زیر به دست می آید:

Post-order:
Traverse the right subtree by recursively calling the post-order function.
Traverse the left subtree by recursively calling the post-order function.
Display the data part of root element (or current element).

postorder(node) 
	if node == null then return
	 postorder(node.right)
	 postorder(node.left)
	 visit(node)

f e – d c – b a + * /

  روش هایی که در بالا  گفتیم به صورت بازگشتی از روی درخت عبارت محاسباتی شکل های infix ، postfix و prefix یک عبارت محاسباتی را حساب می کند.

ولی می توان به صورت مستقیم نمایش prefix و postfix یک عبارت محاسباتی را از روی نمایش infix آن عبارت با استفاده از یک stack (پشته) به دست آورد.

به دست آوردن نمایش postfix از روی نمایش infix با استفاده از stack :

ابتدا از سمت راست شروع به خواندن تک تک اجزای عبارت محاسباتی می کنیم ،که به صورت infix است و به سمت چپ حرکت می کنیم.

یک استک را برای نگه داری عملگرهای در نظر می گیریم. اگر جزیی را که از عبارت خوانده ایم یک عدد یا متغییر است (عملوند) آن را به صورت مستقیم در خروجی چاپ می کنیم. اگر عملگر یا پرانتز بود کار های زیر را انجام می دهیم:

1. اگر پرانتز بسته ” (” بود آن را در استک push  می کنیم.
2. اگر پرانتز باز “)” بود تا زمانی در استک به پرانتز بسته برسیم pop می کنیم و در سر راه هرچه عملگر دیدیم آن را در خروجی چاپ می کنیم.
3. اگر یک عملگر بود و در سر استک پرانتز بسته “(” بود عملگر را در استک push  می کنیم.
4. اگر عملگر بود و در سر استک یک عملگر دیگر موجود بود دو حال وجود دارد اگر عملگری که دیدیدم از عملگری که در سر استک است، اولویت کمتری داشت عملگر سر استک را از استک pop می کنیم و آن را در خروجی چاپ می کنیم  و دوباره چک می کنیم آیا عملگری که دیده ایم با چیزی که سر استک هست اولویتش کمتر است یا نه اگر کمتر بود دوباره همین کار را می کنیم تا زمانی که اولویتش کمتر از عملگر سر استک نباشد و بعد عملگری را که دیده ایم در استک push می کنیم، حالت دوم زمانی اتفاق می افتد که عملگری را که دیده ایم اولویت بیشتری از عملگر سر استک برخوردار باشد در این صورت عملگر جدیدی را که دیده ایم در استک push می کنیم.

اگر تک تک اجزای عبارت را از سمت راست به چپ را دیدیم ولی استک خالی نشده بود تمام محتویات استک را تا زمانی که خالی شود pop می کنیم و عملگرها را در خروجی نمایش می دهیم.

مراحل بالا را برای عبارت داده شده را در زیر می بینید:

همین طور که نمایش postfix عبارت ابتدای متن 

f e – d c – b a + * /

می شود که برابر با postfix است که با پیمایش درخت به دست آوردیم.

به دست آوردن نمایش prefix از روی نمایش infix با استفاده از stack :

دقیقا مانند مرحله ی قبل عمل می کنیم و نمایش postfix را به دست می آوریم سپس خروجی را برعکس می کنیم و نمایش prefix به دست می آید:

f e – d c – b a + * /

–>

/ * + a b – c d – e f

بعدا کد سی پلاس پلاس و جاوااسکریپ الگوریتم های گفته شده را به پست اضافه می کنم.