#逆ポーランド記法とは？
逆ポーランド記法（ぎゃくポーランドきほう、英語: 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}
答えは４
といった読み方(解き方)をしていきます。
#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,結果を返して出力。
って感じです。
実際に実行してみると
(乂'ω')きゅっ ~/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桁同士の計算です。
例えば、
(乂'ω')きゅっ ~/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と同じ
と書くことができます。
ということで実装してみましょう。
#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までご連絡ください。
それでは失礼します