expression.h

重言式是当所有逻辑变元取遍所有值时都为真的表达式。这个程序是用来对重言式进行判别的！还可以吧！牛人别见笑！

#ifndef EXPRESSION_H
#define EXPRESSION_H

#include <string>
#include <stack>
#include <vector>
#include <cassert>
#include <cmath>
#include "logicalelement.h"
#include "BinaryTree.h"
#include "Symbol.h"

class Expression
{
public:
	Expression()
	{
		m_nCounter = 0;
	}

	Expression(std::string strExpression)
	{
		m_nCounter = 0;
		SetExpression(strExpression);
	}
	
	~Expression()
	{
		freeTree (m_pRootNode);
	}

	void SetExpression(std::string const& strExpression)
	{
		if (strExpression.length() > 0)
		{
			m_strExpression = strExpression;
			BuildExpressionTree();
		}
	}

	void GetPostfixExpression(std::string const& strInfix, std::string& strPostfix)
	{
		if (strInfix.length() == 0) 
			throw std::exception("empty expression std::string!");

		std::stack<char> opStack;
		char elem, lastElem;
		std::string str = strInfix;
		str.insert(0, '(');
		str += ')';
		int nLength = str.length();
		strPostfix = "";

		for (int index = 0; index < nLength; index++) 
		{
			elem = str[index];
			if (isalpha(elem)) 
			{
				strPostfix += elem;
				m_varVector.push_back(elem);
			}
			else
			{
				// operator
				if (elem == RIGHT_BRACKET) 
				{
					while ((lastElem = opStack.top()) != LEFT_BRACKET) 
					{
						strPostfix += lastElem;
						opStack.pop();
					}
				}
				else
				{
					if (!opStack.empty()) 
					{
						lastElem = opStack.top();

						if (Precedence(elem, lastElem) > 0) 
						{
							opStack.push(elem);
						}
						else
						{
							do 
							{
								strPostfix += lastElem;
								opStack.pop();
								lastElem = opStack.top(); 
							}
							while (Precedence(elem, lastElem) < 0);
							strPostfix += lastElem;
							opStack.pop();
							opStack.push(elem);
						}
					}
					else
					{
						opStack.push(elem);
					}
				}
			}
		}
	}

	void BuildExpressionTree()
	{
		if (m_strExpression.length() == 0) 
			return;
		
		std::string strPostfix;
		GetPostfixExpression(m_strExpression, strPostfix);

		std::stack<BiTreeNode<char>*> nodeStack;
		int nLength = strPostfix.length();
		char elem;

		for (int index=0; index<nLength; index++)
		{
			elem = strPostfix[index];
			if (isalpha(elem)) 
			{
				BiTreeNode<char>* pNode = new BiTreeNode<char>(elem);
				if (pNode == NULL) 
					throw std::overflow_error("Cannot allocate memory for BiTreeNode!");

				nodeStack.push(pNode);
				if (lookupElement(elem) < 0) 
				{
					m_varVector.push_back(elem);
				}
			}
			else
			{
				if (nodeStack.empty())
					throw std::bad_exception("stack should not be null!");	

				if (elem == NOT) 
				{
					BiTreeNode<char>* pNotNode = nodeStack.top();
					nodeStack.pop();
					BiTreeNode<char>* pNode = new BiTreeNode<char>(elem, pNotNode);
					if (pNode == NULL) 
						throw std::overflow_error("Cannot allocate memory for BiTreeNode!");

					nodeStack.push(pNode);
				}
				else
				{
					BiTreeNode<char>* pRightNode = nodeStack.top();
					nodeStack.pop();
					BiTreeNode<char>* pLeftNode = nodeStack.top();
					nodeStack.pop();

					BiTreeNode<char>* pNode = new BiTreeNode<char>(elem, pLeftNode, pRightNode);
					if (pNode == NULL) 
						throw std::overflow_error("Cannot allocate memory for BiTreeNode!");

					nodeStack.push(pNode);
				}
			}
		}

		if (!nodeStack.empty()) 
		{
			m_pRootNode = nodeStack.top();
			nodeStack.pop();
			assert(nodeStack.empty());
		}
	}

	static int Precedence(char op1, char op2)
	{
		OperatorEnum oe1 = GetOperator(op1);
		OperatorEnum oe2 = GetOperator(op2);
		
		assert (oe1 != wrong && oe2 != wrong);
		return m_precedence[oe1][oe2];
	}

	static int BitMask(int nBase, int nPos)
	{
		int nSeed = 1 << nPos;
		return nBase & nSeed;
	}

	bool IsTrue()
	{
		std::stack<int> varStack;
		int index = m_nCounter = 0;
		int limit = pow(2, m_varVector.size());

		while(m_nCounter <= limit)
		{
			postOrder(m_pRootNode, index, varStack);

			assert (!varStack.empty());
			if (varStack.top() == 0)
				return false;
		}

		return true;
	}

private:

	int lookupElement(char elem)
	{
		int nSize = m_varVector.size();
		for (int index = 0; index < nSize; index++) 
		{
			if (m_varVector[index] == elem)
				return index;
		}

		return -1;
	}

	void postOrder(BiTreeNode<char>* pNode, int index, std::stack<int>& varStack)
	{
		if (pNode != NULL)
		{
			postOrder(pNode->Left(), ++index, varStack);
			postOrder(pNode->Right(), ++index, varStack);
		
			if (isalpha(pNode->Element())) 
			{
				int nLocation = lookupElement(pNode->Element());
				if (nLocation >= 0) 
				{
					varStack.push(BitMask(m_nCounter, nLocation));
				}
				else
				{
					varStack.push(pNode->Element());
				}
			}
			else
			{
				if (pNode->Element() == NOT) 
				{
					assert(!varStack.empty());
					int var = varStack.top();
					varStack.pop();
					var = !var;
					varStack.push(var);
				}
				else
				{
					int var1 = varStack.top();
					varStack.pop();
					int var2 = varStack.top();
					varStack.pop();

					varStack.push(Compute(var1, var2, pNode->Element()));
				}
			}
		}            
	}

	void freeTree(BiTreeNode<char>* pNode)
	{
		if (pNode != NULL) 
		{
			freeTree(pNode->Left());
			freeTree(pNode->Right());
			delete pNode;
		}
	}

	static int m_precedence[5][5];

	enum OperatorEnum { and, or, not, left, right, wrong };

	static int Compute(int var1, int var2, char op)
	{
		switch(op) 
		{
			case AND :
				return var1 & var2;
			
			case OR :
				return var1 | var2;

			default:
				return -1;
		}
	}

	static OperatorEnum GetOperator(char ch)
	{
		switch(ch) 
		{
			case AND :
				return and;
			case OR :
				return or;
			case NOT :
				return not;
			case LEFT_BRACKET:
				return left;
			case RIGHT_BRACKET:
				return right;

			default:
				return wrong;
		}
	}

private:
	int m_nCounter;
	std::string m_strExpression;
	BiTreeNode<char>* m_pRootNode;
	std::vector<char> m_varVector;
};

int Expression::m_precedence[5][5] = 
{
	{-1, 1, -1, 1, -1},
	{-1, -1, -1, 1, -1},
	{1, 1, -1, 1, -1},
	{1, 1, 1, 1, -1},
	{-1, -1, -1, 1, -1}
};

#endif