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

#逆ポーランド記法とは？

>逆ポーランド記法（ぎゃくポーランドきほう、英語: Reverse Polish Notation, RPN）は、数式やプログラムの記法の一種。演算子を被演算子の後にすることから、後置記法 (Postfix Notation) とも言う。
その他の記法として、演算子を被演算子の中間に記述する中置記法、前に記述する前置記法（ポーランド記法）がある
参照:[wikipedia 逆ポーランド記法](https://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95)

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

```c
3 + 6
```
という書き方です。
前置記法だと

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

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

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

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

```c
(3+5)/(1+1)//この答えは4です
```
これを後置記法にすると

```c
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言語で実装
ということで実装してしました。

```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,結果を返して出力。
って感じです。
実際に実行してみると

```cui: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言語で実装(複数桁の計算)
行うべきことは
複数の見分け方です。
これに関しては正直なんでもいいですが今回は[,]で見分けをつけたいと思います。
例えば

```c:
123,77,+//123 + 77と同じ
```
と書くことができます。
ということで実装してみましょう。

```c: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](https://twitter.com/PotyaExe?lang=ja)までご連絡ください。
それでは失礼します