ارزيابی عبارات

صفحه بعد صفحه قبل

يکی از کاربردهای پشته در تبديل عبارت ميانوندی به پسوندی و پيدا کردن مقدار يک عبارت پسوندی است.

عبارت
تبديل عبارت ميانوندی به پسوندی
ارزيابی يك عبارت پسوندی
ارزيابی پرانتزهای پرانتزهای يك عبارت
تبديل عبارات

عبارت

يك عبارت (expressions) از عملگرها(operators)، عملوندها(operamds) و پرانتز ساخته شده است. يك عبارت به شكل مي‌تواند نمايش داده شود:

• ميانوندی (infix) : عملگر بين عملوندهايش قرار مي‌گيرد(A+B)
• پسوندی (postfix) : عملگر بعد عملوندهايش قرار مي‌گيرد(+AB)
• پيشوندی (prefix) : عملگر قبل عملوندهايش قرار مي‌گيرد(AB+)

مثال.

Infix	PostFix	Prefix
16 / 2	16 2 /	/ 16 2
(2 + 14) * 5	2 14 + 5 *	* + 2 14 5
2 + 14 * 5	2 14 5 * +	* 2 + 14 5
(6 - 2) * (5 + 4)	6 2 - 5 4 + *	* - 6 2 + 5 4

روش معمول برای نوشتن يک عبارت روش ميانوندی است. در يک عبارت ميانوندی ترتيب اجرای ارزيابی عملگرها با توجه به الويت های قراردادی و پرانتزگذاری تعيين می شود. کامپايلر برای محاسبه يک عبارت ميانوندی آنرا از شکل ميانوندی به پسوندی تغيير می دهد، زيرا روش پسوندی نيازی به پرانتز گذاری ندارد و الويت هم مطرح نيست. عبارت ميانوندی از چپ به راست پويش می شود، عملوندها در پشته قرار می گيرند و برای ارزيابی عملگر به تعداد لازم عملوند از پشته برداشته می شود و نتيجه مجدد در پشته ذخيره می شود. به اين ترتيب ارزشيابی عبارت پسوندی ساده تر از عبارت ميانوندی انجام می گيرد.

تبديل عبارت ميانوندی به پسوندی

الگوريتم زير عبارت ميانوندی Q را به عبارت پسوندی P تبديل می کند. الگوريتم از پشته برای نگهداری موقت عملگرها و پرانتزهای باز استفاده می کند. در ابتدا يک پرانتز باز در پشته و يک پرانتز بسته در انتهای عبارت Q اضافه می شود. الگوريتم تا خالی شدن پشته تکرار می شود. عبارت Q از چپ به راست پيمايش می شود. هر عنصر عبارت اگر عملوند بود به P و اگر عملگر يا پرانتز باز بود به پشته اضافه می شود. اگر در عبارت به پرانتز بسته برسيم از پشته تا پرانتز باز را برداشنه و به P اضافه می کنيم. پرانتز باز هم از پشته برداشته می شود. وقتی به عملگری می رسيم، اگر الويت آن از الويت عملگر بالای پشته كمتری يا مساوی بود، عملگر بالای پشته را برداشته و به P اضافه می کنيم. اين عمل را اين قدر انجام مي دهيم تا زماني كه عملگر جديد اولويت بيشتری از عملگر بالای پشته داشته باشد. سپس آنرا به پشته اضافه می کنيم.

الگوريتم تبديل عبارت ميانوندی به پسوندی

i:=j:=0;
Q:=Q+')'; P=''; Push('(')
while (not IsEmpty())
  if (Q[i] is an Operand)
    P[j]=P[j]+Q[i]
    j:=j+1;
  else if (Q[i] = '(' )
    push('(')
  else if (Q[i] = ')' )
    while ( Stack[top]<>'(' )
     Pop(x)
     P[j]=P[j]+x
     j:=j+1;
    end while
    Pop(x)
  else if (Q[i] is an Operator)
    while (Precedence (Q[i]) <= Precedence (Stack[Top]))
     Pop(x)
     P[j]=P[j]+x
     j:=j+1
    end while
    Push(Q[i])
  end if
  i:=i+1
end while

مثال. مراحل تبديل عبارت ميانوندی Q به عبارت پسوندی توسط پشته.

ارزيابی يك عبارت پسوندی

برای ارزيابی يک عبارت پسوندی، از چپ به راست عبارت پويش مي‌شود عملوندها در پشته اضافه می شوند. اگر در عبارت به عملگر برسيم دو عنصر از پشته برداشته عملگر روی آنها انجام شده نتيجه مجدد در پشته اضافه می شود. در انتها نتيجه عبارت در بالای پشته است.

الگوريتم ارزيابی عبارات پسوندی

i:=0;
P:=P+')';
while ( P[i}<>')' )
  if (P[i] is an Operand)
    Push(P[i])
  Else if (P[i] is an Operator )
    Pop(B)
    Pop(A)
    Push(AB)
  end if
  i:=i+1
end while

مثال. مراحل ارزيابی عبارت پسوندی P توسط پشته.

ارزيابی پرانتزهای يك عبارت

از پشته می توان برای بررسی ميزان بودن پرانتزهای باز و بسته يک عبارت ميانوندی نيز استفاده کرد. عبارت ميانوندی از چپ به راست پويش می شود. پرانتز بازها در پشته اضافه می شوند. وقتی به پرانتز بسته رسيديم از پشته يک پرانتز باز را بر می داريم، دراين زمان اگر پشته خالی باشد به اين معنی است که تعداد پرانتزهای بسته بيشتر از پرانتز باز بوده است. در انتهای عبارت اگر پشته خالی باشد پرانتزها ميزان بوده اند اگر پرانتز بازی در پشته باقی مانده باشد يعنی تعداد پرانتز بازها از پرانتز بسته ها بيشتر بوده است.

Balance:=True
i:=0
while (Balance = True and i<=Length(Q))
  if (Q[i] = '(' )
    Push('(')
  else if (Q[i] = ')' )
    if (IsEmpty() )
      Balance = false
    else
      Pop(x);
    end if
  i:=i+1
end while
if (IsEmty() )
  Expression is Balanced
end if