数据结构-用栈实现简单的计算器

阅读数: 次 2020-10-15
语言：C++

IDE：Xcode

实现方式：栈(由链表实现)
//编写该程序需要知道后缀表达式的相关知识，包括中缀表达式如何转化为后缀表达式，后缀表达式如何计算

#include <iostream>
#include <string>
#include <cmath>  //求幂函数需要用到C语言中的pow()函数

using namespace std;

template<class T>
class Link_stack //带有头结点的栈，pTop指向头结点，头结点的下一个节点是栈顶
{
private:
    struct Node{
        T data;
        Node* pNext;
        
        Node():pNext(NULL){};
        Node(const T& x, Node* node = NULL):data(x), pNext(node){};
        ~Node(){};
    };
    
    Node* pHead;
    Node* pTop;
    
public:
    Link_stack(){
        pHead = new Node;
        pTop = pHead;
    }
    ~Link_stack();
    void push(const T& x);
    const T pop();
    void traverse()const;
    bool IsEmpty() const;
    T top() const;
};

template<class T>
Link_stack<T>::~Link_stack()
{
    Node* p = pHead->pNext;
    Node* temp;
    while(p)
    {
        temp = p;
        p = p->pNext;
        delete temp;
    }
    
    p = NULL;
    delete pHead;
    pTop = NULL;
}

template<class T>
void Link_stack<T>::push(const T& x)
{
    Node* temp = new Node(x, pTop->pNext);
    pTop->pNext = temp;
}

template<class T>
const T Link_stack<T>::pop()
{
    if(pTop->pNext == NULL)
    {
        cout << "Stack is empty!" << endl;
        exit(-1);
    }
    
    Node* temp = pTop->pNext;
    pTop->pNext = temp->pNext;
    T value = temp->data;
    delete temp;
    return value;
}

template<class T>
void Link_stack<T>::traverse()const
{
    if(pTop->pNext == NULL)
    {
        cout << "Stack is empty!" << endl;
        exit(-1);
    }
    
    Node* p = pTop->pNext;
    while(p)
    {
        cout << p->data << " ";
        p = p->pNext;
    }
}

template<class T>
bool Link_stack<T>::IsEmpty() const
{
    if(pTop->pNext == NULL)
        return true;
    else
        return false;
}

template<class T>
T Link_stack<T>::top() const
{
    return pTop->pNext->data;
}


//下面实现计算器类
template<class T>
class calc
{
private:
    string expression;
    string::iterator itr_front = expression.begin(); //string类的迭代器
    string::iterator itr_back = expression.end();    //string类的迭代器
    //enum枚举，该例子相信可以加深对枚举类型的印象
    enum token{OPAREN, ADD, SUB, MULTI, DIV, EXP, CPAREN, VALUE, EOL};
    
    //Binaryop取出运算数栈中的两个元素，执行相应的运算，将运算结果放入运算数栈
    void Binaryop(token op, Link_stack<T>& DataStack);
    
    //Getop函数从表达式的当前位置开始取出一个合法的符号
    token Getop(T& value);
    
public:
    calc(string str):expression(str){}
    ~calc(){}
    T result();
};

template<class T>
void calc<T>::Binaryop(token op, Link_stack<T>& DataStack)
{
    T num1, num2;
    
    if(DataStack.IsEmpty())
    {
        cerr << "缺右运算数！" << endl;
        exit(-1);
    }
    else
        num2 = DataStack.pop();
    
    if(DataStack.IsEmpty())
    {
        cerr << "缺左运算数！" << endl;
        exit(-1);
    }
    else
        num1 = DataStack.pop();
    
    switch(op)
    {
        case ADD:
            DataStack.push(num1 + num2);
            break;
        case SUB:
            DataStack.push(num1 - num2);
            break;
        case MULTI:
            DataStack.push(num1 * num2);
            break;
        case DIV:
            DataStack.push(num1 / num2);
            break;
        case EXP:
            DataStack.push(pow(num1,num2));
    }
    
}

template<class T>
typename calc<T>::token calc<T>::Getop(T& value)
{
    
    while(*itr_front == ' ')
        ++itr_front;
    
    if(itr_front == itr_back)
        return EOL;
    
    if(*itr_front >= '0' && *itr_front <= '9')
    {
        value = 0;
        while(*itr_front >= '0' && *itr_front <= '9')
        {
            value = value * 10 + (*itr_front - '0');
            ++itr_front;
        }
        return VALUE;
    }
    
    
    switch(*itr_front)
    {
        case '(': ++itr_front; return OPAREN;
        case '+': ++itr_front; return ADD;
        case '-': ++itr_front; return SUB;
        case '*': ++itr_front; return MULTI;
        case '/': ++itr_front; return DIV;
        case '^': ++itr_front; return EXP;
        case ')': ++itr_front; return CPAREN;
    }
   
    exit(-1);
}

template<class T>
T calc<T>::result()
{
    token lastOp, topOp;
    T result_value, current_value;
    Link_stack<token> opStack;
    Link_stack<T> dataStack;
    
    while((lastOp = Getop(current_value)) != EOL)
    {
        switch(lastOp)
        {
            case VALUE:
                dataStack.push(current_value);
                break;
            case CPAREN:
                while(!opStack.IsEmpty() && (topOp = opStack.pop()) != OPAREN)
                    Binaryop(topOp, dataStack);
                if(topOp != OPAREN)
                    cerr << "缺左括号！" << endl;
                break;
            case OPAREN:
                opStack.push(lastOp);
                break;
            case EXP:
                opStack.push(EXP);
                break;
            case MULTI:
            case DIV:
                while(!opStack.IsEmpty() && opStack.top() >= MULTI)
                    Binaryop(opStack.pop(), dataStack);
                opStack.push(lastOp);
                break;
            case ADD:
            case SUB:
                while(!opStack.IsEmpty() && opStack.top() != OPAREN)
                    Binaryop(opStack.pop(), dataStack);
                opStack.push(lastOp);
        }
    }
    
    while(!opStack.IsEmpty())
        Binaryop(opStack.pop(), dataStack);
    
    if(dataStack.IsEmpty())
    {
        cerr << "无结果！" << endl;
        exit(-1);
    }
    
    result_value = dataStack.pop();
    
    if(!opStack.IsEmpty())
    {
        cerr << "缺操作符！" << endl;
        exit(-1);
    }
    
    return result_value;
    
}


//测试函数
int main()
{
    calc<int> test1("3*(1+1)^2^3/(4-2)-10");
    cout << test1.result() << endl; //输出374
    
    calc<int> test2("6/3*4+1");
    cout << test2.result() << endl; //输出9
    
    return 0;
}