您的位置: 首页  >  文章  >  使用二叉树求四则混合运算表达式

使用二叉树求四则混合运算表达式

分类: 文章 • 2024-01-20 12:45:07

kagula

2019-3-24

main.cpp

演示如何调用

#include <cstdlib>
#include <string>
#include <iostream>

#include "Node.h"
#include "Builder.h"
#include "ExpBuilder.h"
#include "ExpParser.h"
#include "StackBasedCalVisitor.h"

using namespace std;

int main(int argc, char** argv) {
    ExpBuilder builder;
    ExpParser parser;

    parser.setBuilder(&builder);
    string input="(((30+500)*70)-(60/50))";//输入表达式
    parser.parse(input);
    Node* root = builder.getExpression();
    cout<<input<<endl;
    root->print();

    StackBasedCalVisitor sbsv;
    root->Accept(&sbsv);
	cout << endl << "StackBasedSumVisitor Result: " << sbsv.getResult() << endl;

	assert(37098.9 == sbsv.getResult());//验证运算结果
    return 0;
}

UML类图

用Visio2019画了下，感觉效果不太好。

使用二叉树求四则混合运算表达式

下面是依赖文件

Builder.h

#ifndef BUILDER_H
#define BUILDER_H
#include "Node.h"
#include <string>

class Builder{
public:
    virtual void addOperand(string operand)=0;
    virtual void addLiteral(string literal)=0;
    virtual void addLeftParenthesis()=0;
    virtual void addRightParenthesis()=0;
    virtual Node* getExpression()=0;
};

#endif /* BUILDER_H */

ExpBuilder.h

#ifndef EXPRESSIONBUILDER_H
#define EXPRESSIONBUILDER_H
#include <stack>
#include <iostream>
#include <assert.h>

#include "Node.h"
#include "Builder.h"

class ExpBuilder: public Builder{
protected:
    stack<Node*> expStack;
public:
	~ExpBuilder()
	{
	}
    void addOperand(string operand) override{
        expStack.push(new Node(operand));
    };
    
    void addLiteral(string literal) override {
        Node* newLiteral = new Node(literal);

		if (expStack.size() == 0)
		{
			expStack.push(newLiteral);
			return;
		}
		else if (expStack.size() == 1)
		{
			expStack.push(newLiteral);
			return;
		}
		else if (expStack.size() >= 2)
		{
			if (isON())
			{
				Node* root = expStack.top(); expStack.pop();
				root->setLeftChild(newLiteral);

				//because division's result depend the order, so right element must be in right child node.
				Node* rightNode = expStack.top(); expStack.pop();
				root->setRightChild(rightNode);

				expStack.push(root);
				return;
			}
			expStack.push(newLiteral);
		}
    };
    
    void addLeftParenthesis() override {
		if (expStack.size() == 0)
		{
			assert(NULL);
		}
		else if (expStack.size() == 1)
		{
			Node* rightParenthesis = expStack.top(); expStack.pop();
			if (rightParenthesis->getValue() == ")")
				return;
			assert(NULL);
		}
		else if (expStack.size() >= 2)
		{
			Node* root = expStack.top(); expStack.pop();
			Node* rightParenthesis = expStack.top(); expStack.pop();
			if (rightParenthesis->getValue() == ")")
			{
				expStack.push(root);
			}
			else if (rightParenthesis->getValue() == "+" ||
				rightParenthesis->getValue() == "-" || 
				rightParenthesis->getValue() == "*" || 
				rightParenthesis->getValue() == "/" )
			{
				Node* pOperator = rightParenthesis;
				pOperator->setLeftChild(root);
				
				Node* rightNumber = expStack.top(); expStack.pop();
				pOperator->setRightChild(rightNumber);

				Node* rightParenthesis = expStack.top(); expStack.pop();
				if (rightParenthesis->getValue() != ")")
				{
					assert(NULL);
				}

				expStack.push(pOperator);
			}
			else
			{
				assert(NULL);
			}
		}
	};
    
    void addRightParenthesis() override {
		expStack.push(new Node(")"));
    };
    
    Node* getExpression() override {
		if (expStack.size() > 0)
		{
			Node* root = expStack.top();
			expStack.pop();
			return root;
		}
		return nullptr;
    };
private:
	//Operator, Number
	bool isON()
	{
		Node* maybeO = expStack.top(); expStack.pop();
		Node* maybeN = expStack.top(); expStack.push(maybeO);

		bool isOperator = false;
		if (maybeO->getValue() == "+" || maybeO->getValue() == "-" || maybeO->getValue() == "*" || maybeO->getValue() == "/")
		{
			isOperator = true;
		}

		bool isNumber = this->isNumber(maybeN->getValue());

		if (isOperator && isNumber)
		{
			return true;
		}
		return false;
	}

	bool isNumber(std::string str)
	{
		for (int i = 0; i < str.size(); i++)
		{
			if ( (str[i] <= '9' && str[i] >= '0') || str[i] == '.')
				continue;
			return false;
		}
		return true;
	}
};

#endif /* EXPBUILDER_H */

ExpParser.h

#ifndef PARSER_H
#define PARSER_H
#include <string>
#include <iostream>
#include "Builder.h"

#include <list>

enum class DATA_TYPE {
	UNKNOWN, DIGITAL, OPERATOR, PARENTHESIS
};

class ExpParser {
protected:
	Builder* m_expBuilder;
public:
	void setBuilder(ExpBuilder* builder) {
		m_expBuilder = builder;
	}

	void parse(string exp) {
		//transform to element list
		auto filter = [](ExpParser *pThis, string exp)->std::list<string>
		{
			list<string> listResult;
			string strLiteral;

			int i = exp.size() - 1;
			while (i >= 0)
			{
				const char cTemp = exp[i];
				if (pThis->getType(cTemp) == DATA_TYPE::PARENTHESIS || pThis->getType(cTemp) == DATA_TYPE::OPERATOR)
				{
					if (strLiteral.empty() == false)
					{
						listResult.push_back(strLiteral), strLiteral = "";
					}
					listResult.push_back(pThis->c2str(cTemp));
				}
				else if (pThis->getType(cTemp) == DATA_TYPE::DIGITAL)
				{
					strLiteral.insert(0, pThis->c2str(cTemp));
				}

				i--;
			}//while

			if (strLiteral.empty() == false)
			{
				listResult.push_back(strLiteral), strLiteral = "";
			}

			return listResult;
		};
		list<string> elements = filter(this, exp);

		//store to binary tree
		for (list<string>::iterator iter = elements.begin();
			iter != elements.end(); iter++)
		{
			string element = *iter;
			if (getType(element) == DATA_TYPE::PARENTHESIS)
			{
				if (element[0] == '(')
				{
					m_expBuilder->addLeftParenthesis();
				}
				else if (element[0] == ')')
				{
					m_expBuilder->addRightParenthesis();
				}
			}
			else if (getType(element) == DATA_TYPE::OPERATOR)
			{
				m_expBuilder->addOperand(c2str(element[0]));
			}
			else if (getType(element) == DATA_TYPE::DIGITAL)
			{
				m_expBuilder->addLiteral(element);
			}
		}
	}

private:
	DATA_TYPE getType(const char c)
	{
		if ((c == '+') || (c == '-') || (c == '*') || (c == '/'))
		{
			return DATA_TYPE::OPERATOR;
		}

		if ((c == '(') || (c == ')'))
		{
			return DATA_TYPE::PARENTHESIS;
		}

		if (isdigit(c))
			return DATA_TYPE::DIGITAL;

		return DATA_TYPE::UNKNOWN;
	}

	DATA_TYPE getType(const string c)
	{
		if (c.size() == 0)
		{
			assert(NULL);
		}
		if (c.size()==1)
		{
			return getType(c[0]);
		}


		for (size_t i = 0; i < c.size(); i++)
		{
			if (getType(c[i]) != DATA_TYPE::DIGITAL)
				return DATA_TYPE::UNKNOWN;
		}

		return DATA_TYPE::DIGITAL;
	}

	string c2str(const char c)
	{
		string strT;
		strT.push_back(c);
		return strT;
	}
};


#endif /* EXPPARSER_H */

Node.h

#ifndef NODE_H
#define NODE_H
#include <string>
#include <iostream>

#include "Visitor.h"

using namespace std;

class Node{
protected:
    string m_value;
    Node* m_leftChild;
    Node* m_rightChild;
public:
    Node(string value):m_value(value), m_leftChild(NULL), m_rightChild(NULL){}
    virtual ~Node(){
        if(!m_leftChild) delete m_leftChild;
        if(!m_rightChild) delete m_rightChild;
    }
    string getValue(){ 
        return m_value;
    }
    void setLeftChild(Node* left){ 
        m_leftChild = left;
    }
    void setRightChild(Node* right){ 
        m_rightChild = right;
    }
    Node* getLeftChild() const { 
        return m_leftChild;
    }
    Node* getRightChild() const { 
        return m_rightChild;
    }
    void print(){
        if(m_leftChild){
            cout<<"(";
            m_leftChild->print();
        }
        cout<<m_value;
        if(m_rightChild){
            m_rightChild->print();
            cout<<")";
        }
    }
    void Accept(Visitor* visitor){
        visitor->getNum(this);
    }
};

#endif /* NODE_H */

Visitor.h

#ifndef VISITOR_H
#define VISITOR_H
class Node;

class Visitor{
public:
    Visitor() {}
    virtual ~Visitor() {}
    double getResult() {
        return result;
    }
    virtual void getNum(Node *ptr) = 0;
protected:
    double result = 0;
};


#endif /* VISITOR_H */

StackBasedCalVisirot.h

#ifndef STACKBASEDCALVISITOR_H
#define STACKBASEDCALVISITOR_H
#include "Node.h"
#include "Visitor.h"

#include <stack>

class StackBasedCalVisitor:public Visitor{
public:
    StackBasedCalVisitor() {};
    virtual ~StackBasedCalVisitor() {};
    void getNum(Node *ptr) override{
		result = calculate(ptr);
    }

	double calculate(Node *pNode)
	{
		if (pNode->getValue()=="+")
		{
			return calculate(pNode->getLeftChild()) + calculate(pNode->getRightChild());
		} 
		else if (pNode->getValue() == "-")
		{
			return calculate(pNode->getLeftChild()) - calculate(pNode->getRightChild());
		}
		else if (pNode->getValue() == "*")
		{

			return calculate(pNode->getLeftChild()) * calculate(pNode->getRightChild());
		}
		else if (pNode->getValue() == "/")
		{

			return calculate(pNode->getLeftChild()) / calculate(pNode->getRightChild());
		}

		double dVal = std::stod(pNode->getValue());

		if (pNode->getLeftChild() != nullptr)
		{
			assert(NULL);
		}

		if (pNode->getRightChild() != nullptr)
		{
			assert(NULL);
		}

		return dVal;
	}
};

#endif /* STACKBASEDCALVISITOR_H */

类似的需求，比如说实现这个算法，更适合采用工作流的方法来进行设计， 现在这种样子， 代码看上去反而不太容易理解。我觉的面向对象设计只适合偏向业务流需求的解。

相关推荐