【练习】c++用链栈实现计算器

「爱情、让人受尽委屈。」 2022-10-22 04:13 131阅读 0赞

栈有顺序栈和链栈，其中顺序栈相当于用数组表示，而链栈则用链表，在表现方式上用链栈当然更加复杂。  
首先对于一个链栈，自己重写类，需要写的基本的函数：构造函数，析构函数，入栈操作，出栈操作，取栈头，判断栈空，（判断栈满的操作对于链栈没有实际意义），其中的数据元素有指向下一个元素的结点指针和当前的元素个数。  
上代码：

## 定义模板类 ##

#include<string>
    #include<iomanip>
    #define maxlen 1000
    
    template <class T>
    struct node
    { 
        T data;    // 元素字段 
        node* next;           // 指针字段
    };
    
    template <class T>
    class  stack{ 
    public:
       
        stack();
        ~stack();                           // 初始化
        bool empty()  const { 
            if (countt == 0) return true;
            else return false;
        };     // 判断空
        bool full()  const { 
            if (countt == maxlen) return true;
            else return false;
        };          // 判断满
        T top()  const;
        // 取栈顶元素
        void push(T x) { 
            if (full())return;
         
    
            countt++;
            node<T>* p = new node<T>;
    
            p->data = x;
        // p->next = NULL;
            p->next = first;
           first=p;
    
    
        }    //入栈
        void pop();             // 出栈
      // 栈的数据成员;
    private:
        int countt;
        node<T>* first = new node<T>;
    
    };

其中要注意node\* first,而不是node\*< T>  
(当模板类的数据成员中有模板结构体时的 处理方式）

## 成员函数的实现： ##

template <class T>
    stack<T> ::~stack()
    { 
      // node<T>*p = first;
        node<T>* u = new node<T>;
        while (!empty()) { 
           
            u = first;
            first = first->next;
            delete u;
         // pop();
            countt--;
        }
      
    };
    
    template <class T>
    stack<T> ::stack()
    { 
        countt = 0;
        first = nullptr;
    };
    template <class T>
    T stack<T>::top() const{ 
       int m = countt - 1;
      // node<T>* p = first->next;
    
       return first->data;
    }
    template <class T>
    void stack<T>::pop() { 
        if (empty())return;
        node<T>* p = first;
        first= first->next;
        delete p;
        countt--;
    
      // first = first->next;
    
    }

## 对于计算器的实现采用中缀转后缀表达式： ##

class cal { 
    public:
    
    
        double comppost();
        bool trans(string exp);
        void getfromclient(string& m)
        { 
            cin >> m;
            int si = m.size();
            exp = new char[si];
            post = new char[si];
    
        }
    private:
        char* post;
        char* exp;
        double result;
    };
    
    
    bool cal::trans(string expp)
    { 
    
        stack<char>st;
    
        int k = 0, i = 0, j = 0;
        while (expp[j] != '\0')
        { 
            if (expp[j] == 'C')
            { 
    
                j++;
                i--;
    
                continue;
            }
            else if (expp[j] == 'A')
            { 
    
                system("cls");
                return false;
            }
            else if (expp[j] == '=')
            { 
                exp[i++] = expp[j++];
                break;
            }
            else { 
                exp[i++] = expp[j++];
    
    
            }
    
        }
        exp[i] = '\0';
        
    
        while (exp && (*exp != '='))
        { 
    
            switch (*exp)
            { 
            case '(':
                st.push(*exp);
                exp++;
                break;
            case ')':
                while (!st.empty() && st.top() != '(')
                { 
                    post[k++] = st.top();
                    st.pop();
                }
                st.pop();//弹出“（”符号
                exp++;
                break;
            case '+':
            case '-':
                while (!st.empty())
                { 
                    if (st.top() != ')')
                    { 
                        post[k++] = st.top();//若栈顶不是（则将栈顶放入post中
                        st.pop();//出栈
                    }
                    else
                        break;//如果栈顶元素是'('时退出循环
                }
                st.push(*exp);
                exp++;
                break;
            case '*':
            case '/':
                while (!st.empty())
                { 
                    if (st.top() == '*' || st.top() == '/')
                    { 
                        post[k++] = *exp;
                        st.pop();
                    }
                    else
                        break;
                }
                st.push(*exp);
    
                exp++;
                break;
    
            default:
                while (*exp >= '0' && *exp <= '9')
                { 
                    post[k++] = *exp;
                    exp++;
    
                }
                post[k++] = '#';//用#标识一个数字串结束 比如32这样的多位数
            }
        }
        while (!st.empty())//将运算符放入post中
        { 
            post[k++] = st.top();
            st.pop();
        }
        post[k] = '\0';//给post表达式添加结束符
        return true;
    }
    double cal::comppost()//计算后缀表达式的值
    { 
        double a, b, c;
        stack<double>st;
        while (*post)
        { 
            switch (*post)
            { 
            case '+':
                a = st.top(); st.pop();
                b = st.top(); st.pop();
                c = a + b;
                st.push(c);
                break;
            case '-':
                a = st.top(); st.pop();
                b = st.top(); st.pop();
                c = b - a;
                st.push(c);
                break;
            case '*':
                a = st.top(); st.pop();
                b = st.top(); st.pop();
                c = a * b;
                st.push(c);
                break;
            case '/':
                a = st.top(); st.pop();
                b = st.top(); st.pop();
                if (a == '0')
                { 
                    cout << "error!";
                    exit(1);
                }
                else
                    c = b / a;
                st.push(c);
                break;
            default:
                double d = 0;
                while (*post >= '0' && *post <= '9')
                { 
                    d = d * 10 + *post - '0';
                    post++;
                }
                st.push(d);
                break;
            }
            post++;
        }
    
        return st.top();
    }
    
    int main()
    { 
    
        string input;
    
        cal put;
        double res;
        put.getfromclient(input);//用户接口
    
        if (put.trans(input))//计算引擎
        { 
            res = put.comppost();
            cout << res;
        }
        else
    
            cout << "已清零\n";
    
        
    
       
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]: /images/20221022/56258ffba10a4a41a534bf8a20ef015d.png