====== 9月3日追加問題 ======

====== 問題07 逆ポーランド計算機(Stackの応用) ======

前問で作成したスタックのデータ構造を使って、ちょっとしたプログラムを作ってみる。 前の問題を参考に、int型のデータを格納できる15個の長さ（深さ）を持ったstackを考えます。 それを使って以下のアルゴリズムで逆ポーランド記法で記述された算術式を計算するアルゴリズムを実装します。

 
[[https://www.mathblog.dk/tools/infix-postfix-converter/|参考）数式を入力すると、逆ポーランド記法に変換してくれるよ。]]
\\

== アルゴリズム ==

  -  記号付きリスト 逆ポーランド記法で書かれている数式を左から順に**単語ごとに**読む
  -  **数字を読み取った場合：**数値をスタックにPush
  -  記号付きリスト **記号(+, -, *, /)を読み取った場合**：
     * スタックから**2つの数値**をPop
     * 先にPopした値を a , 次にPopした値を b として
     * 読み取った記号を使い　a 記号 b を計算する
     * 計算結果をスタックにpush
  - 式がおわるまで上記の作業2, 3を繰り返す
  -  式のすべての単語を処理後，スタックに残っている値が計算結果

逆ポーランド記法で記述された整数の計算の数式が与えられるので、関数Push、Popを使ってアルゴリズムに従って計算を行い、数式をすべて処理し終えたときの、計算結果、総push回数、総pop回数を表示する（最後の結果を取得するためのpopを含む）。



===== 入力 =====

以下のようなフォーマットで１行で数式が与えられる。（例は　中置記法では　(1+2)*(3-4)　）

<code>
算術演算子
加算： +
減算： -
乗算： *
除算： /
例）
1 2 + 3 4 - *
</code>

===== 出力 =====

<code>
１行目：計算結果
２行目：Push回数
３行目：Pop回数
</code>

===== 制約 =====

  * スタックの深さは15とする ・入力は整数値＋算術演算記号（+, -, *, / ) 
  * ソースコードは以下のものを使い、指定の場所だけを書き換えることとする。 
（他は完成しているから、書き換えなくともよい）

=== ソースコード ===

<code cpp>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using std::endl;
using std::cout;
using std::cin;
using std::setw;
using std::string;
using std::vector;


void initStack();
void push(const int _val);
int pop();
void printCurrentStack();

//constant number for stack length 
const int Length = 15;

//data chank for construction of stack
//for integer values
int stack_dat[Length];

//stack pointer(global variable)
//It indicates current data on the stack
int sp = 0;

void initStack()
{
    for (auto i = 0; i < Length; i++)
        stack_dat[i] = 0;
    //initializing all stack factor by filling Zero(integer) 
}

//push a data to stack
void push(const int _val)
{
    stack_dat[sp] = _val;
    sp++;
}
//pop a data from stack
//poped data is deleted from stack 
int pop()
{
    int tmp = stack_dat[--sp];
    stack_dat[sp] = 0;
    return tmp;
}

//今回は使わないけど3桁ずつで整数スタックを表示する関数
//確認作業の時に使ってください
void printCurrentStack()
{
    for (int i = 0; i < Length; i++)
    {
        cout << "|" << setw(3) <<stack_dat[i];
    }
    cout << "|" << endl;
}

int main()
{
    int push_count = 0;//push回数を数えるカウンタ変数
    int pop_count = 0;//pop回数を数えるカウンタ変数
   
    //ここに逆ポーランド記法の計算をスタックを使ってごにょごにょするプログラムを書く
       
    //最後の計算結果を取得して表示→pop回数＋１
    cout << pop() << endl;
    pop_count += 1;
    cout << push_count << endl;//総push回数
    cout << pop_count << endl;//総pop回数

}
</code>

==== ヒント ====

=== スペース区切り文字列の入力 ===

aaa bbb ccc ddd

のように、最後が改行文字で終了する入力を、1文字列ごとに読み込むには、読込用のstirngを用意しておいて以下のように処理するとよい。 cinは読み込みに成功するとtrue失敗するとfalseを返すので、文字絵列を読込失敗した時点でループから抜けるようになる。（正確には正しくないんだけど、そう覚えておいてもいい気がする）

<code cpp>
#include <string>

std::string tmp;

while(cin >> tmp)
{
    
}
//これでも大丈夫なはず
//char temp[100];//100文字分は多いかもしれない。適宜合わせる
//while(cin >> temp)
//{
//
//}
</code>

コマンドプロンプトで1行入力をするときは、うまく行の終わりがプログラムに伝わらないので、以下のようにする

1行入力終了後、最後改行してから、次の行の冒頭で　**Ctrl＋z** を押す。

オンラインジャッジ上では、while(cin >> tmp)でうまく1行入力できるので特に何もしなくてよいです。

=== 文字列から数値への変換 ===

整数を表す数字の入った文字列、すなわち”128”,“15”,“8”などを、数値の128, 15, 8 に変換するには、文字列整数変換の関数stoiを使う。

<code cpp>
//std::stringで処理するバージョン
#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::cin;
using std::endl;

int main() {
  string tmp;
  int a,b;

  cin >> tmp; //文字列として読込
  a = stoi(tmp);//整数に変換
  cin >> tmp;//文字列として読込
  b = stoi(tmp);//整数に変換

  cout << a << " + " << b <<" = " << a + b << endl;
  //整数に変換されているので、足し算ができる
}
//char *tmp
//har tmp[]
//で処理するバージョン
//int main()
//{
//  char tmp[15];
//  int a, b;
//
//  cin >> tmp;
//  string s = tmp;//これでなぜかstringに変換される
//  a = stoi(s);
//  cin >> tmp;
//  s = tmp;//これでなぜかstringに変換される
//  b = stoi(s);
//  cout << a << " + " << b <<" = " << a + b << endl;
//}
</code>

整数と文字列の変数用意しておいて、その都度、整数の読み込みと文字の読み込み分ければいいじゃん、と思うかもしれないが、それはとても難しい。。。 なので、今回は、算術記号の他は整数値の文字列しか出てこないので、算術記号以外＝数値を表す文字列ということで読み込みを分岐させるとすっきりしそう。

===== 入力例 1 =====

<code>
1 2 +
</code>

===== 出力例 1 =====

<code>
3
3
3
</code>

===== 入力例 2 =====

<code>
34 116 + 20 5 - 5 - 1 * +
</code>

===== 出力例 2 =====

<code>
160
11
11
</code>