今回は優先順が決まった要素（オペレータ、オペランド）をその場で木構造に組んでそれを一つのオペランド要素として処理を続行するやり方で、逆ポーランド記法への並べ替えとツリー構造の構築を同時に行うことにしました。
取り敢えず符号 (+ -) 演算子と 四則演算(+ - * /) が使えるようにした実験プログラムを作成して、完成した木構造を逆ポーランド記法で印字してみて気づいたことが・・・
逆ポーランド記法だと符号 (+ -) と加減算 (+ -) の区別がつかない (・・? 、そういえば逆ポーランド記法の説明で符号を扱ったものを見たこと無いような・・・
実験プログラムソース
// compiler Visual C++ 2019
// 式評価実験プログラム
#include <iostream>
#include <vector>
#include <map>
#include <stack>
// 式アイテム基底クラス
struct exp_item : public std::enable_shared_from_this<exp_item>
{
using ptr_type = typename std::shared_ptr<exp_item>; // ポインタタイプ
using ctr_type = typename std::vector<ptr_type>; // コンテナタイプ
// 演算子型
enum class ope_type_enum
{
open,
operand,
plus,
minus,
mul,
div,
add,
sub,
close,
} ope_type;
// 演算子情報
struct ope_info
{
int priority; // 優先度
int order; // 順序 0:左→右 1:左←右
int num; // オペランド数
int code; // 記述コード
};
// 演算子情報テーブル
static const std::map<ope_type_enum, ope_info> ope_info_map;
exp_item() : ope_type(ope_type_enum::operand) {}
virtual ~exp_item() {}
// 枝コンテナ取得
virtual ctr_type& branch() { throw "未実装例外"; }
// 優先度判定
// 評価順と演算子優先度から判断し、対象の優先度が高い場合 true
virtual bool priority(ptr_type tag)
{
if (ope_info_map.at(ope_type).order == 0)
{
return ope_info_map.at(ope_type).priority >= ope_info_map.at(tag->ope_type).priority;
}
else
{
return ope_info_map.at(ope_type).priority > ope_info_map.at(tag->ope_type).priority;
}
}
virtual bool parse(std::istream& is, ptr_type node) = 0;
virtual int calc() = 0;
virtual void print(std::ostream& os) = 0;
// 空白文字を読み飛ばす
static void trim(std::istream& is)
{
while (is)
{
auto c = is.peek();
if (!is.good()) break;
if (c == '\n') break;
if (!std::isspace(c)) break;
is.get();
}
return;
}
};
const std::map<exp_item::ope_type_enum, exp_item::ope_info> exp_item::ope_info_map = {
{exp_item::ope_type_enum::open, {0, 0, 1, '('}}, // 開き括弧（未実装）
{exp_item::ope_type_enum::operand, {1, 0, 0, -1}}, // オペランド
{exp_item::ope_type_enum::plus, {2, 1, 1, '+'}}, // + 符号
{exp_item::ope_type_enum::minus, {2, 1, 1, '-'}}, // - 符号
{exp_item::ope_type_enum::mul, {3, 0, 2, '*'}}, // 乗算
{exp_item::ope_type_enum::div, {3, 0, 2, '/'}}, // 除算
{exp_item::ope_type_enum::add, {4, 0, 2, '+'}}, // 加算
{exp_item::ope_type_enum::sub, {4, 0, 2, '-'}}, // 減算
{exp_item::ope_type_enum::close, {0, 0, 0, ')'}}, // 閉じ括弧（未実装）
};
// リテラル値アイテムクラス
struct exp_literal : exp_item
{
int value;
virtual ~exp_literal() {}
virtual bool parse(std::istream& is, ptr_type node)
{
trim(is);
auto c = is.peek();
if (!std::isdigit(c))
{
return false;
}
is >> value;
if (!is.good())
{
return false;
}
node->branch().push_back(shared_from_this());
return true;
}
virtual int calc()
{
return value;
}
virtual void print(std::ostream& os)
{
os << " " << value;
}
};
// 演算子アイテムクラス
struct exp_operator : public exp_item
{
ctr_type branch_;
virtual ~exp_operator() {}
virtual ctr_type& branch()
{
return branch_;
}
virtual bool parse(std::istream& is, ptr_type node)
{
trim(is);
auto c = is.peek();
ope_type = ope_type_enum::operand;
// 演算子情報テーブルを検索して演算子型を決定する
// この時点では + - は全て符号扱い
for (const auto& item : ope_info_map)
{
if (item.second.code == c)
{
ope_type = item.first;
break;
}
}
if (ope_type == ope_type_enum::operand)
{
return false;
}
is.get();
node->branch().push_back(shared_from_this());
return true;
}
virtual int calc()
{
switch (ope_type)
{
case ope_type_enum::plus:
return branch()[0]->calc();
case ope_type_enum::minus:
return - branch()[0]->calc();
case ope_type_enum::mul:
return branch()[0]->calc() * branch()[1]->calc();
case ope_type_enum::div:
return branch()[0]->calc() / branch()[1]->calc();
case ope_type_enum::add:
return branch()[0]->calc() + branch()[1]->calc();
case ope_type_enum::sub:
return branch()[0]->calc() - branch()[1]->calc();
}
throw "論理エラー";
}
virtual void print(std::ostream& os)
{
for (auto item : branch())
{
item->print(os);
}
os << " " << (char)ope_info_map.at(ope_type).code;
}
};
// 式クラス
struct expression : public exp_item
{
ptr_type exp = nullptr;
virtual ~expression() {}
virtual bool parse(std::istream& is, ptr_type node = nullptr)
{
// 式項目の取り出し・記述順項目リスト作成
auto items = ptr_type{ new exp_operator }; // 記述順項目リスト作成用アイテム
while (is)
{
if (ptr_type{ new exp_operator }->parse(is, items))
{
continue;
}
if (ptr_type{ new exp_literal }->parse(is, items))
{
continue;
}
break;
}
if (items->branch().size() == 0)
{
return false;
}
// オペランドの直後の + -（符号）は加減算に変更する
for (auto ite = items->branch().begin(); ite < items->branch().end() - 1; ++ite)
{
if ((*ite)->ope_type == ope_type_enum::operand)
{
if ((*(ite + 1))->ope_type == ope_type_enum::plus)
(*(ite + 1))->ope_type = ope_type_enum::add;
if ((*(ite + 1))->ope_type == ope_type_enum::minus)
(*(ite + 1))->ope_type = ope_type_enum::sub;
}
}
// 木構造構築
std::stack<ptr_type> sk1; // 優先順スタック
std::stack<ptr_type> sk2; // オペランドスタック
// 記述順項目リストから順番に取り出して処理する
for (auto ite = items->branch().begin(); ite < items->branch().end(); ++ite)
{
if (sk1.empty())
{
sk1.push(*ite);
continue;
}
// 処理中項目と優先順スタック先頭項目が共にオペランドの場合はエラー
if (((*ite)->ope_type == ope_type_enum::operand) &&
(sk1.top()->ope_type == ope_type_enum::operand))
{
throw "演算子不足";
}
// 処理中項目より優先度が高い項目を優先順スタックから全て取り出す
while (!sk1.empty() && (*ite)->priority(sk1.top()))
{
auto item = sk1.top();
sk1.pop();
if (item->ope_type != ope_type_enum::operand)
{
// 取り出した項目が演算子ならオペランドスタックから必要数取り出して枝に追加する
for (auto n = 0; n < ope_info_map.at(item->ope_type).num; ++n)
{
if (sk2.empty())
throw "オペランド不足";
item->branch().insert(item->branch().begin(), sk2.top());
sk2.pop();
}
}
// 取り出した項目をオペランドスタックに積む
sk2.push(item);
}
// 記述順項目を優先順スタックに積む
sk1.push(*ite);
}
// 優先順スタック残項目を吐き出す
while (!sk1.empty())
{
auto item = sk1.top();
sk1.pop();
if (item->ope_type != ope_type_enum::operand)
{
// 取り出した項目が演算子ならオペランドスタックから必要数取り出して枝に追加する
for (auto n = 0; n < ope_info_map.at(item->ope_type).num; ++n)
{
if (sk2.empty())
throw "オペランド不足";
item->branch().insert(item->branch().begin(), sk2.top());
sk2.pop();
}
}
sk2.push(item);
}
// オペランドスタック残項目チェック
if (sk2.size() < 1)
throw "論理エラー";
if (sk2.size() > 1)
throw "演算子不足";
// オペランドスタックに残ったアイテム（式のルートアイテム）を取得する
exp = sk2.top();;
return true;
}
virtual int calc()
{
if (exp == nullptr)
throw "計算式なし";
return exp->calc();
}
virtual void print(std::ostream& os)
{
if (exp == nullptr)
return;
exp->print(os);
}
};
int main()
{
std::cout << "[Ctrl]+[Z]で終了" << std::endl;
while (std::cin)
{
std::cout << "> ";
expression exp;
try
{
if (exp.parse(std::cin))
{
std::cout << "逆ポーランド表記：";
exp.print(std::cout);
std::cout << std::endl;
std::cout << "計算結果：" << exp.calc() << std::endl;
}
}
catch (const char* s)
{
std::cout << std::string(s) << std::endl;
}
if (std::cin.peek() == '\n')
std::cin.get();
}
return 0;
}
- 実行画面
- exp_test1.png (11.96 KiB) 閲覧数: 67 回
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター