Edited at

逆ポーランド記法を理解するために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までご連絡ください。

それでは失礼します