とりあえず数式を計算させてみた
こんにちは。
前回、構文解析木を作ったのですが、とりあえず計算させてみたいということで進めてみます。
ちょっと中途半端な感じです。
逆ポーランド記法の数式を文字列として返す
うーん、木構造のクラスに逆ポーランド記法を返すという特殊な用途のメソッドを入れたくないのですが、入れてしまいます。
#pragma once
#include"MyStack.h"
#include"MyQueue.h"
#include<sstream>
template<typename T>
class MyTreeNode
{
public:
MyTreeNode(T element,MyTreeNode<T>* left,MyTreeNode<T>* right) {
this->_element = element;
this->_left = left;
this->_right = right;
}
T getElement() {
return this->_element;
}
MyTreeNode<T>* getLeft() {
return this->_left;
}
MyTreeNode<T>* getRight() {
return this->_right;
}
void setLeft(MyTreeNode<T>* left) {
this->_left = left;
}
void setRight(MyTreeNode<T>* right) {
this->_right = right;
}
static string traverse(MyTreeNode<T>* node) {
ostringstream ss;
if (node->getLeft() != nullptr) {
ss << traverse(node->getLeft());
}
if (node->getRight() != nullptr) {
ss << traverse(node->getRight());
}
ss << " " << node->getElement()->getToken();
return ss.str();
}
static string order_string(string order, MyTreeNode<T>* node) {
ostringstream ss;
if (order == "pre") {
ss << node->getElement()->to_string() << " ";
}
if (node->getLeft() != nullptr) {
ss << order_string(order, node->getLeft());
}
if (order == "in") {
ss << node->getElement()->to_string() << " ";
}
if (node->getRight() != nullptr) {
ss << order_string(order, node->getRight());
}
if (order == "post") {
ss << node->getElement()->to_string() << " ";
}
return ss.str();
}
static string depthFirst(MyTreeNode<T>* node) {
MyStack<MyTreeNode<T>*>* st = new MyStack<MyTreeNode<T>*>();
MyTreeNode<T>* tmp;
ostringstream ss;
st->push(node);
while (!st->empty()) {
tmp = st->pop();
ss << tmp->getElement()->to_string() << " ";
if (tmp->getRight() != nullptr) {
st->push(tmp->getRight());
}
if (tmp->getLeft() != nullptr) {
st->push(tmp->getLeft());
}
}
return ss.str();
}
static string breadthFirst(MyTreeNode<T>* node) {
MyQueue<MyTreeNode<T>*>* qu = new MyQueue<MyTreeNode<T>*>();
MyTreeNode<T>* tmp;
ostringstream ss;
qu->offer(node);
while (!qu->isEmpty()) {
tmp = qu->poll();
ss << tmp->getElement() << " ";
if (tmp->getLeft() != nullptr) {
qu->offer(tmp->getLeft());
}
if (tmp->getRight() != nullptr) {
qu->offer(tmp->getRight());
}
}
return ss.str();
}
private:
T _element;
MyTreeNode<T>* _left;
MyTreeNode<T>* _right;
};
とりあえず追加したのは、３６～５０行目です。
逆ポーランド記法の数式を計算する
以前とほとんど同じですが、小数点を扱えるように変更します。
また、剰余計算ができるようにも変更します。
#pragma once
#include"MyStack.h"
#include<iostream>
using namespace std;
class MyReversePolishNotation
{
public:
MyReversePolishNotation(){
this->_st = new MyStack<double>();
}
double calc(string s){
string tmp = "";
double result;
for (int i = 0; i < s.size();i++){
if(s[i]==' '){
if(tmp!=""){
this->_st->push(stod(tmp));
}
tmp = "";
continue;
}
if(isdigit(s[i]) || s[i]=='.'){
tmp += s[i];
continue;
}
tmp += s[i];
if(_st->empty()){
throw runtime_error("Formula error");
}
double v2 = _st->pop();
if(_st->empty()){
throw runtime_error("Formula error");
}
double v1 = _st->pop();
if(tmp=="+"){
result = v1 + v2;
} else if(tmp=="-"){
result = v1 - v2;
} else if(tmp=="*"){
result = v1 * v2;
} else if(tmp=="/"){
result = v1 / v2;
} else if(tmp=="%"){
result = (int)v1 % (int)v2;
} else {
throw runtime_error("Formula error");
}
this->_st->push(result);
tmp = "";
}
result = _st->pop();
if(!_st->empty() || tmp!=""){
throw runtime_error("Formula error");
}
return result;
}
private:
MyStack<double>* _st;
};
計算させてみよう
とりあえず計算させるプログラムを載せます。
途中に、字句解析の結果、構文解析の結果も出力するようにしています。
#include"MyLexer.h"
#include"MyParser.h"
#include"MyReversePolishNotation.h"
#include<string>
#include<iostream>
using namespace std;
int main(){
string inEx;
cin >> inEx;
MyLexer* l = new MyLexer(inEx);
MyQueue<MyASTNode *> *res1 = l->getTokens();
cout << res1->to_string() << endl;
MyParser *p = new MyParser();
p->parse(res1);
MyTreeNode<MyASTNode *> *res2 = p->getAst();
string ex = MyTreeNode<MyASTNode *>::traverse(res2);
cout << MyTreeNode<MyASTNode *>::order_string("post", res2) << endl;
cout << ex <<endl;
MyReversePolishNotation* res3 = new MyReversePolishNotation();
cout << res3->calc(ex) <<endl;
}
実行結果
それでは、いくつか計算させてみます。
実行結果１（１行目は入力）
5%4+3*2-1
[(1,numeral)] → [(-,operator2)] → [(2,numeral)] → [(*,operator1)] → [(3,numeral)] → [(+,operator2)] → [(4,numeral)] → [(%,operator1)] → [(5,numeral)]
(5,numeral) (4,numeral) (%,operator1) (3,numeral) (2,numeral) (*,operator1) (+,operator2) (1,numeral) (-,operator2)
5 4 % 3 2 * + 1 -
6
実行結果２（1行目は入力）
(12.3+4.5)*6.7-(8.901+2.345)*6
[(6,numeral)] → [(*,operator1)] → [(),rightPar)] → [(2.345,numeral)] → [(+,operator2)] → [(8.901,numeral)] → [((,leftPar)] → [(-,operator2)] → [(6.7,numeral)] → [(*,operator1)] → [(),rightPar)] → [(4.5,numeral)] → [(+,operator2)] → [(12.3,numeral)] → [((,leftPar)]
(12.3,numeral) (4.5,numeral) (+,operator2) (6.7,numeral) (*,operator1) (8.901,numeral) (2.345,numeral) (+,operator2) (6,numeral) (*,operator1) (-,operator2)
12.3 4.5 + 6.7 * 8.901 2.345 + 6 * -
45.084
うーん、プログラムがいまいち。
今回はこれでおしまいにします。それではまた。