β

模板栈以及中缀表达式求值(C++实现)

碧远|bystander 1440 阅读

栈直接用链表实现,这个比较简单,不多说,不过C++写程序,IDE的错误检测不是很给力。

至于给定一个中缀表达式,如何不转换成后缀表达式,直接求值,方法就是使用两个栈,一个操作符栈,一个操作数栈,然后从左到右扫描表达式,我这里中缀表达式计算实现的很简单,不完整,大家可以扩展。栈的实现是我想写的,思路如下:

1.如何是操作数,压入操作数栈

2.如果是操作符,压入操作符栈

3.如果是左括号,直接忽略

4.如果是有括号,弹出操作符栈栈顶元素,然后弹出操作数栈两个元素,进行操作以后结果压入操作数栈

看个图就好了

最后给出栈顶实现代码

#include "stdafx.h"
#pragma region Node定义

template <class T>
class Node
{
	template<class T> 
	friend class Stack;
private:
	T m_data;
	Node *pNextNode;
public:
	Node();
	Node(T d);
};

template <class T>
Node<T>::Node()
{
	m_data=default(T);
	pNextNode=NULL;
}
template <class T>
Node<T>::Node(T d)
{
	m_data=d;
	pNextNode=NULL;
}
#pragma endregion 

#pragma region Stack定义

template <class T>
class Stack
{

private:
	Node<T> *m_pTopNode;
	int m_nNodeCount;
public:
	Stack();
	~Stack();
	bool IsEmpty();
	bool Push(T e);
	T Pop();
	int Size();
};

template <class T>
Stack<T>::Stack() : m_pTopNode(NULL),m_nNodeCount(0)
{
}

template <class T>
Stack<T>::~Stack()
{
	while (!IsEmpty())
	{
		Node<T> *pTempNode = m_pTopNode;
		m_pTopNode = m_pTopNode->pNextNode;
		delete (pTempNode);
		pTempNode = NULL;
	}
	m_nNodeCount = 0;
	m_pTopNode = NULL;
}

template <class T>
bool Stack<T>::IsEmpty()
{
	return (m_pTopNode == NULL);
}

template <class T>
bool Stack<T>::Push(T e )
{
	Node<T> *pNewNode = new Node<T>(e);
	if (NULL == pNewNode)     {
		return false;
	}

	if(! IsEmpty()) {
		pNewNode->pNextNode = m_pTopNode;
	}
	m_pTopNode = pNewNode;
	m_nNodeCount ++;

	return true;
}

template <class T>
T Stack<T>::Pop()
{
	if(IsEmpty()) {
		return T(-1);
	}
	T e;
	e = m_pTopNode->m_data;
	Node<T> *pNode = m_pTopNode;
	m_pTopNode = m_pTopNode->pNextNode;
	delete (pNode);
	m_nNodeCount--;

	return e;
}

template <class T>
int Stack<T>::Size()
{
	return m_nNodeCount;
}
#pragma endregion

然后是main函数代码

int _tmain(int argc, _TCHAR* argv[])
{
	string str;
	str="(1+((2+3)*(4*5)))";
	for (int i=0;i<str.length();i++)
	{
		char s=str[i];
		if (s=='(') ;
		else if (s=='+') ops.Push(s);
		else if (s=='*') ops.Push(s);
		else if (s==')') 
		{
			char op = ops.Pop();
			if (op=='+') 
				vals.Push(vals.Pop() + vals.Pop());
			else if (op=='*') 
				vals.Push(vals.Pop() * vals.Pop());
		}
		else 
			vals.Push(s-'0');
	}
	cout<<(vals.Pop());
	return 0;
}

另外,今天是博客建站一周年.加油!

作者:碧远|bystander
寻找窄门
原文地址:模板栈以及中缀表达式求值(C++实现), 感谢原作者分享。

发表评论