C
逆ポーランド記法

逆ポーランド記法を理解するためにC言語で実装してみた

逆ポーランド記法とは?

逆ポーランド記法(ぎゃくポーランドきほう、英語: Reverse Polish Notation, RPN)は、数式やプログラムの記法の一種。演算子を被演算子の後にすることから、後置記法 (Postfix Notation) とも言う。
その他の記法として、演算子を被演算子の中間に記述する中置記法、前に記述する前置記法(ポーランド記法)がある
参照:wikipedia 逆ポーランド記法

上記に引用した中置記法は皆さんがよく使う

3 + 6

という書き方です。
前置記法だと

+ 3 6

と演算子を最初に書いて被演算子(数字)をその後に書くといった記法をします。
今回理解する後置記法は

3 6 +

と被演算子を最初に書きその後に演算子を書く記法です。

記法 どう記述する? ex.
前置記法 演算子を被演算子の前に記述する +36
中置記法 演算子を被演算子の中間に記述する 3+6
後置記法 演算子を被演算子の後に記述する 36+

逆ポーランド記法の読み方

逆ポーランド記法はもともとポーランド記法をコンピュータに適応させるために作られたものです。
逆ポーランド記法だったら被演算子だったらスタックに値を入れて(push)、演算子だったらスタックから値を取り出す(pop)というのを繰り返すだけでよくなりますね。
それでは、実際に解いてみましょう。
例として以下の中置記法を用意します。

(3+5)/(1+1)//この答えは4です

これを後置記法にすると

35+11+/

となります。
読み方(解き方)としては、({}はスタック)
0, 左から順に読んでいく
1, 3をスタックに入れる{3}
2, 5をスタックに入れる{3 5}
3, +になるのでスタックから3と5を取り出し、演算子にあった計算(今回は加算)を行い計算結果をスタックに入れる{8}
4, 1をスタックにいれる{8 1}
5, 1をスタックにいれる{8 1 1}
6, +になるのでスタックから1と1を取り出し、演算子にあった計算(今回は加算)を行い計算結果をスタックに入れる{8 2}
7, /になるのでスタックから8と2を取り出し、演算子にあった計算(今回は除算)を行い計算結果をスタックに入れる{4}
答えは4

といった読み方(解き方)をしていきます。

c言語で実装

ということで実装してしました。

Reverse_Polish_Notation.c
#include <stdio.h>

char rpn(char pol_f[100]);

int c2i(char c);
char i2c(int i);

void push(char stack[100], int *sp, char c);
char pop(char stack[100], int *sp);


int main(void)
{
    char pol_f[100];
    char dmy;

    printf("Input Reverse Poland : ");
    scanf("%s%c", pol_f, &dmy); 

    printf("Ans : %d\n", c2i(rpn(pol_f)));

    return 0;
}               

char rpn(char pol_f[100])
{
    char stack[100];
    int sp = 0;
    int i;
    char first, second;

    for ( i = 0; pol_f[i] != '\0'; i++) {
        if ( '9' >= pol_f[i] && pol_f[i] >= '1' ) {
            push(stack,&sp,pol_f[i]);

        } else {
            if (pol_f[i] == '+') {
                second = pop(stack, &sp);
                first = pop(stack, &sp);
                push(stack, &sp, i2c(c2i(first) + c2i(second)));
            } else if  (pol_f[i] == '-') {
                    second = pop(stack, &sp);
                first = pop(stack, &sp);
                push(stack, &sp, i2c(c2i(first) - c2i(second)));

            } else if  (pol_f[i] == '*') {
                    second = pop(stack, &sp);
                first = pop(stack, &sp);
                push(stack, &sp, i2c(c2i(first) * c2i(second)));
            } else  if  (pol_f[i] == '/'){
                    second = pop(stack, &sp);
                first = pop(stack, &sp);
                push(stack, &sp, i2c(c2i(first) / c2i(second)));

            }
        }
    }

    return pop(stack, &sp);
}

int c2i(char c)
{
    return c - '0';
}

char i2c(int i)
{
    return '0' + i;
}

void push(char stack[100], int *sp, char c)
{
    stack[(*sp)++] = c;
}

char pop(char stack[100], int *sp)
{
    return stack[--*sp];
}

流れとしましては、
1,scanfで逆ポーランド記法で入力してもらう。
2,上でやった解き方を行う。
3,結果を返して出力。
って感じです。
実際に実行してみると

a.out
(乂'ω')きゅっ ~/algorithm  ./a.out                                   [] └('ω')┘ニャアアアアアアアアアア!!!! 
Input Reverse Poland : 12+
Ans : 3

(乂'ω')きゅっ ~/algorithm  ./a.out                                   [] └('ω')┘ニャアアアアアアアアアア!!!! 
Input Reverse Poland : 122++
Ans : 5

(乂'ω')きゅっ ~/algorithm  ./a.out                                   [] └('ω')┘ニャアアアアアアアアアア!!!! 
Input Reverse Poland : 1981+++
Ans : 19

といった感じでしっかり計算ができています。
が、少し問題があります。それは計算をするときに1桁同士の計算しかできません。
実際に上記の計算は全て1桁同士の計算です。
例えば、

a.out
(乂'ω')きゅっ ~/algorithm  ./a.out                                   [master] └('ω')┘ニャアアアアアアアアアア!!!! 
Input Reverse Poland : 100+34*/
zsh: segmentation fault (core dumped)  ./a.out

~/algorithm master* ⇡ 7s
(乂'ω')きゅっ ~/algorithm  ./a.out                                   [master] └('ω')┘ニャアアアアアアアアアア!!!! 
Input Reverse Poland : 100+456++
zsh: segmentation fault (core dumped)  ./a.out

って感じだとエラーが出ちゃいます(書き方ミスってる感じもするけど)

ということで修正をしましょう。

c言語で実装(複数桁の計算)

行うべきことは
複数の見分け方です。
これに関しては正直なんでもいいですが今回は[,]で見分けをつけたいと思います。
例えば

123,77,+//123 + 77と同じ

と書くことができます。
ということで実装してみましょう。

New_Reverse_Polish_Notation.c
#include <stdio.h>

int rpn(char pol[]);
void push(int *sp, int stack[], int value);
int pop(int *sp, int stack[]);


int main(void)
{
    char pol[100];
    char dmy;

    printf("Input Reverse Poland : ");
    scanf("%s%c", pol, &dmy);   

    printf("Ans : %d\n", rpn(pol));

    return 0;
}               

int rpn(char pol[])
{
    int stack[100];
    int sp = 0;
    int i;
    int value = 0;
    int _1stValue;
    int _2ndValue;

    for ( i = 0; pol[i] != '\0'; i++) {
        if ( '1' <= pol[i] && pol[i] <= '9' ) {
            while(pol[i]!=','){ 
            value= (value * 10)+(pol[i]-'0');
            i++;
            }
                        push(&sp,stack,value);  
                value = 0;


        } else {
            if (pol[i] == '+') {
                _2ndValue = pop(&sp, stack);
                _1stValue = pop(&sp, stack);
                push(&sp, stack, _1stValue + _2ndValue);
            } else if  (pol[i] == '-') {
                _2ndValue = pop(&sp, stack);
                _1stValue = pop(&sp, stack);
                push(&sp, stack, _1stValue - _2ndValue);
            } else if  (pol[i] == '*') {
                _2ndValue = pop(&sp, stack);
                _1stValue = pop(&sp, stack);
                push(&sp, stack, _1stValue * _2ndValue);
            } else { // if  (pol[i] == '/')
                _2ndValue = pop(&sp, stack);
                _1stValue = pop(&sp, stack);
                push(&sp, stack, _1stValue / _2ndValue);
            }
        }
    }

    return pop(&sp, stack);
}

void push(int *sp, int stack[], int value)

{
    stack[(*sp)++] = value;
}

int pop(int *sp, int stack[])
{
    return stack[--*sp];
}

whileのところで[,]が来るまで10倍(入力されたchar型をint型に変更)するというプログラムなのでとりあえずこれで完了です。

まとめ

前置記法、中置記法、後置記法の3つの記法が存在する。
逆ポーランド記法はポーランド記法をコンピュータに適応させるために作られた記法。
C言語で実装は疲れた。
ゴリ押しダメ。絶対

何か質問等ありましたら@PotyaExeまでご連絡ください。
それでは失礼します