用C++实现模板栈和中缀表达式求值教程

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

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

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

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

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

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

看个图就好了



最后给出栈顶实现代码

#include “stdafx.h”

pragma region Node定义

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

template
Node::Node()
{
m_data=default(T);
pNextNode=NULL;
}
template
Node::Node(T d)
{
m_data=d;
pNextNode=NULL;
}
pragma endregion
pragma region Stack定义

template
class Stack
{

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

template
Stack::Stack() : m_pTopNode(NULL),m_nNodeCount(0)
{
}

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

template
bool Stack::IsEmpty()
{
return (m_pTopNode == NULL);
}

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

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

return true;

}

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

return e;

}

template
int Stack::Size()
{
return m_nNodeCount;
}
pragma endregion

然后是main函数代码

int _tmain(int argc, _TCHAR argv[])
{
    string str;
    str=”(1+((2+3)(45)))”;
    for (int i=0;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;
}