言語処理系論

逆ポーランド記法

数式を表す方法として逆ポーランド記法がある。この方法では例えばa+bはab+と表される。
計算機中ではカッコを使わずに一意に式を解釈できることからこの方法が用いられる。

逆ポーランド記法で計算できる電卓のアルゴリズム

• • 一文字づつ読み込んでいく
    • 数字が来た場合 そのままスタックにpushする。
    • 演算子が来た場合　スタックから二つpopして演算子を用いて計算した結果をpushする。

　//逆ポーランド電卓
　#define STACK_SIZE 100
　int stack[STACK_SIZE];　
　int n;

　void error(char *s){

 printf("error\n");

 exit(1);

　}

　void init(){
　 n=0;
　}

　void push(int x){

　 if(x>=STACK_SIZE)
　   printf("stack overflow\n");

　　 stack[n++]=x;
　　}

　　int pop(){

　　 if(n<=0)printf("error\n");
　　 return stack[--n];　

　　　}

　　int empty(){

　　 return n==0;

　}

　int main(){

 int c;
 int x,a,b;
 init();
 while((c=getchar())!=EOF){
   if(isdigit(c)){
     ungetc(c,stdin);//一旦読み込んだ文字を読み込まなかったことにして
                   //ストリームに返す
     scanf("%d",&x);
     push(x);
   }else{

     switch(c){
     case '+':
b=pop();a=pop();
push(a+b);
break;
     case '-':
b=pop();a=pop();
push(a-b);
break;
     case '*':
b=pop();a=pop();
push(a*b);
break;
     case '/':
b=pop();a=pop();
push(a/b);
break;
     case '\n':
if(!empty())
  printf("answer=%d",pop());
init();
break;
     case ' ':
     case '\t':
break;
     } 
   }
 }

　　}
　　}