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

栈直接用链表实现,这个比较简单,不多说,不过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-&gt;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)*(45)))“;
    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;
}
另外,今天是博客建站一周年.加油!

comments powered by Disqus