[C言語アルゴリズム]後置記法(または逆ポーランド記法)

#C言語で後置記法(逆ポーランド記法)アルゴリズムを実装した
##学習にあたって使用した環境

• ideone.com (https://ideone.com/)
  ※オンライン上でプログラミング学習ができるサイト

##参考資料
C言語による最新アルゴリズム辞典 (奥村晴彦著/1991年初版 技術評論社：72ページ)

##後置記法の概要
以下参考資料より引用

式"(a+b)(c-d)"を読み上げる際、かっこを省略して"a足すb掛けるc引くd"と読めば
あいまいであるが、"aとbの和とcとdの差との積"とよむとあいまいでなくなる。
このような記法を後置記法または逆ポーランド記法という。
この語順のまま記号を書けば"ab+cd-"となる。

後置記法の演算においては、

"a"は"aの値をスタックに積む"と解釈し、
"+"はスタックから"ab値を2個下ろしその和をスタックに積む"と解釈すれば、
最後にスタックに1個だけ残る値が答えである。

##ソースコード

一般的な"(a+b)*(c-d)"のような記法を挿入記法(infix notation)という。
挿入記法を用いた式を後置記法(postfix notation)に直す。

• 元の式中の空白は読み飛ばす。
• 数式の間違いがあった場合には"?"を出力する。

postfix.c

/* 後置記法 postfix notation */
/* 逆ポーランド記法ともいう */

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

int ch;

// 1文字読込する関数
// 半角スペースとタブは読み飛ばす
void readchar(void){
    do {
        if((ch = getchar()) == EOF){
            return;
        } 
    } while(ch == ' ' || ch == '\t');
}

void expression(void);

// 数学における"因子"を表す関数
void factor(void){
    // chの値が'('か')'の場合
    if(ch == '('){
        readchar();
        expression();
        ch == ')' ? readchar() : putchar('?');
    } 
    // 文字が空白 (' ') を除く表示文字 (printing character)の場合
    else if(isgraph(ch)){
		// 1文字書き出す
        putchar(ch);
        readchar();
    } else{
        putchar('?');
    }
}

// 数学における"項"を表す関数
void term(void){
    factor();
    for(;;){
        if (ch == '*'){
            readchar();
            factor();
    
            // *を書き出す
            putchar('*');
    
        } else if (ch == '/'){
            readchar();
            factor();
    
    		// /を書き出す
            putchar('/');
    
        } else{
            break;
        }
    }
}

// 数学における"式"を表す関数
void expression(void){

    term();

    // +か-の場合にはもう一文字読み込んでからputcharする
    for(;;){
        if(ch == '+'){
            readchar();
            term();
            
            // +を書き出す
            putchar('+');
            
        }else if(ch == '-'){
            readchar();
            term();
            
            // -を書き出す
            putchar('-');
            
        }else{
            break;
        }
    }
}

int main(void) {
    // 終端までループ
	do {
		readchar();
        expression();

        //  改行文字か終端までループ
        while(ch != '\n' && ch != EOF){
            putchar('?');
            readchar();
        }
        // 改行文字を入れる
        putchar('\n');

	} while(ch != EOF);
	
	return EXIT_SUCCESS;
}

##実行結果

#1/stdin.txt(任意)

(2+1)*(4-3)

#1/stdout.txt(任意)

21+43-*

#2/stdin.txt(任意)

(1+1)+(2+2)

#2/stdout.txt(任意)

11+22++

#4/stdin.txt(任意)

(2*(1+2))*5

#4/stdout.txt(任意)

212+*5*

式がおかしい時には?を出力する。

#5/stdin.txt(任意)

1+*2

#5/stdout.txt(任意)

1*+?

##補足
このプログラムで行っているのは「再帰的下向き構文解析」というものらしい。
自由文脈文法に対する構文解析法の一つ。

##所感

• ひとつひとつの処理はシンプルでも、再帰処理になると複雑になる。
• 構文解析の中で"木"の概念が登場するので、次は木について取り上げたい。
• 私自身は高校の数学をドロップアウトした数学弱者であるが、勉強し直してみようと思う。