تماس درباره   صفحه اصلی
  ساختمان داده > ارزشيابي عبارات  
 
 

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


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

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


عبارت

يك عبارت (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 به عبارت پسوندی توسط پشته.

Convert Infix to Postfix

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

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

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

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 توسط پشته.

Evaluate Postfix

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

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

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


تبديل عبارات

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

1. عبارت كامل پرانتزگذاری می‌ شود
2. هر عملگر به سمت راست پرانتز باز خود منتقل می شود
3. پرانتزها حذف می شوند

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

1. عبارت كامل پرانتزگذاری می‌ شود
2. هر عملگر به سمت چپ پرانتز بسته خود منتقل می شود
3. پرانتزها حذف می شوند

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

1. ابتدا عبارت پسوندی را تبديل به ميانوندی می ‌كنيم
2. عبارت ميانوندی حاصل را به پيشوندی تبديل می ‌كنيم

نكته. در تبديل عبارات ترتيب عملوندها تغيير نمی‌كند.


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

سوالات چند گزينه ای درباره ارزيابی عبارات


 


 


صفحه اصلی| PDF| درباره| تماس