C言語でのスタック式の評価について説明する

スタックは線形データ構造であり、データは一方の端でのみ挿入および削除されます。

アルゴリズム

以下に、プッシュ（）-

• スタックオーバーフローを確認します。

if (top = = n-1)
printf("stack over flow");

• それ以外の場合は、要素をスタックに挿入します。

top ++
a[top] = item

以下に示すのは、 Pop（）のアルゴリズムです。 −

• スタックのアンダーフローを確認します。

if ( top = = -1)
printf( "stack under flow");

それ以外の場合は、スタックから要素を削除します。

item = a[top]
top --

以下に示すのは、表示（）のアルゴリズムです。 −

if (top == -1)
printf ("stack is empty");

それ以外の場合は、以下のアルゴリズムに従ってください。

for (i=0; i<top; i++)
printf ("%d", a[i]);

スタックの適用

C言語でのスタックの式の変換を理解しましょう。

式-これは、オペランドと演算の合法的な組み合わせです。

式の種類

変換と評価を実行できるC言語の式には3つのタイプがあります。以下に説明します-

• 中置式-演算子はオペランドの間にあります。たとえば、A + B

• プレフィックス式-演算子はオペランドの前にあります。たとえば、+ AB

• 後置式-演算子はオペランドの後にあります。たとえば、AB +

後置式の評価

アルゴリズム

入力文字列を左から右にスキャンします。

入力記号ごとに、

• 数字の場合は、スタックにプッシュします。

• 演算子の場合は、スタックから一番上の2つのコンテンツを取り出して、それらに演算子を適用します。後で、結果をスタックにプッシュします。

• 入力記号が「\0」の場合は、スタックを空にします。

プログラム

以下は、後置式を評価するためのCプログラムです-

#include<stdio.h>
int top = -1, stack [100];
main ( ){
   char a[50], ch;
   int i,op1,op2,res,x;
   void push (int);
   int pop( );
   int eval (char, int, int);
   printf("enter a postfix expression:");
   gets (a);
   for(i=0; a[i]!='\0'; i++){
      ch = a[i];
      if (ch>='0' && ch<='9')
         push('0');
      else{
         op2 = pop ( );
         op1 = pop ( );
         res = eval (ch, op1, op2);
         push (res);
      }
   }
   x = pop ( );
   printf("evaluated value = %d", x);
   getch ( );
}
void push (int n){
   top++;
   stack [top] = n;
}
int pop ( ){
   int res ;
   res = stack [top];
   top--;
   return res;
}
int eval (char ch, int op1, int op2){
   switch (ch){
      case '+' : return (op1+op2);
      case '-' : return (op1-op2);
      case '*' : return (op1*op2);
      case '/' : return (op1/op2);
   }
}

出力

上記のプログラムを実行すると、次の結果が得られます-

Run 1:
enter a postfix expression:45+
evaluated value = 9
Run 2:
enter a postfix expression: 3 5 2 * +
evaluated value = 13