数据结构逆波兰表达式求值

分手后的思念是犯贱 2022-05-23 12:05 228阅读 0赞

mystack头文件代码：

#define MAXSIZE 100
    
    //顺序栈的存储结构
    template <class T>
    struct sqstack
    {
        T *base;
        T *top;
    };
    
    //初始化栈
    template <class T>
    void InitSqstack(sqstack <T> &s)
    {
        s.base = new T[MAXSIZE];
        if(!s.base)
            exit(1);
        s.top = s.base;
    }
    
    //顺序栈压栈
    template <class T, class F>
    void Push(sqstack <T> &s, F e)
    {
        if(MAXSIZE == s.top - s.base)
        {
            cout << "满栈" << endl;
            exit(1);
        }
        *(++s.top) = e;
    }
    
    //顺序栈弹栈
    template <class T>
    void Pop(sqstack <T> &s)
    {
        if(s.top == s.base)
        {
            cout << "空栈" << endl;
            exit(1);
        }
        s.top--;
    }
    
    //顺序栈栈顶
    template <class T>
    T Top(sqstack <T> s)
    {
        if(s.top == s.base)
        {
            cout << "空栈" << endl;
            exit(1);
        }
        return *s.top;
    }
    
    //判断栈是否为空
    template <class T>
    bool EmptySqstack(sqstack <T> s)
    {
        if(s.base == s.top)
            return true;
        else
            return false;
    }
    
    //从栈底输出栈
    template <class T>
    void PrintSqstack(sqstack <T> s)
    {
        while(s.base != s.top)
        {
            ++s.base;
            cout << *s.base;
        }
    }

主函数代码：

#include <iostream>
    using namespace std;
    #include <cctype>
    #include <cstdlib>
    #include "mystack.h"
    /*
            cctype库提供了处理字符串中字符的各种函数
    */
    
    
    char s[101];
    sqstack <char> temporarystack;      //定义临时栈
    sqstack  <char> resultstack;             //定义结果栈
    
    
    //运算符优先级判断
    int OperatorPriorityJ(char ch)
    {
            int grade;
            switch(ch)
            {
                case '+':
                    grade = 1;
                case '-':
                   grade = 1;
                    break;
                case '*':
                    grade = 2;
                case '/':
                    grade = 2;
                    break;
                case '(':
                    grade = 3;
                    break;
                case '=':
                    grade = 0;
                    break;
            }
            return grade;
    }
    
    
    //中缀表达式转为逆波兰表达式
    void TransformReversePolish(char *s)
    {
        Push(temporarystack, '=');
        int count = 0;
        for(int i = 0; '\0' != s[i]; i++)
        {
            if(isdigit(s[i]) || '.' == s[i])
            {
                if(!EmptySqstack(resultstack))
                {
                    Push(resultstack, ' ');
                }
                if(1 == count)
                {
                    Pop(resultstack);
                }
                Push(resultstack, s[i]);
                count = 1;
            }
            else if(')' == s[i])
            {
                count = 0;
                while('(' != Top(temporarystack))
                {
                    Push(resultstack, ' ');
                    Push(resultstack, Top(temporarystack));
                    Pop(temporarystack);
                }
                Pop(temporarystack);
            }
            else if(OperatorPriorityJ(s[i]) > OperatorPriorityJ(Top(temporarystack)))
            {
                count = 0;
                Push(temporarystack, s[i]);
                if('(' == s[i])
                {
                    while(1)
                    {
                        i++;
                        if(isdigit(s[i]) || '.' == s[i])
                        {
                            Push(resultstack, ' ');
                            if(1 == count)
                            {
                                Pop(resultstack);
                            }
                            Push(resultstack, s[i]);
                            count = 1;
                        }
                        else if('(' == Top(temporarystack) || OperatorPriorityJ(s[i]) > OperatorPriorityJ(Top(temporarystack)))
                        {
                            count = 0;
                            Push(temporarystack, s[i]);
                        }
                        else
                        {
                            count = 0;
                            while('(' != Top(temporarystack) && OperatorPriorityJ(s[i]) <= OperatorPriorityJ(Top(temporarystack)))
                            {
                                Push(resultstack, ' ');
                                Push(resultstack, Top(temporarystack));
                                Pop(temporarystack);
                            }
                            Push(temporarystack, s[i]);
                        }
                        if(')' == s[i + 1])
                        {
                            break;
                        }
                    }
                }
            }
            else
            {
                count = 0;
                while(!EmptySqstack(temporarystack) && OperatorPriorityJ(s[i]) <= OperatorPriorityJ(Top(temporarystack)))
                {
                    if('(' == Top(temporarystack))
                    {
                        break;
                    }
                    Push(resultstack, ' ');
                    Push(resultstack, Top(temporarystack));
                    Pop(temporarystack);
                }
                Push(temporarystack, s[i]);
            }
        }
    }
    
    
    //计算
    double Calculate(sqstack <char> s)
    {
        double value;
        char a[16];
        s.base += 1;
        sqstack <double> valuestack;
        InitSqstack(valuestack);
        while(s.base != s.top + 1)
        {
            double num;
            double num1, num2;
            for(int i = 0; i < 15; i++)
            {
                if(isdigit(*s.base) || '.' == *s.base)
                {
                    a[i] = *s.base;
                }
                if(!(isdigit(*s.base) || '.' == *s.base))
                {
                    a[i] = '\0';
                    break;
                }
                s.base++;
            }
            if('\0' != a[0])
            {
                num = atof(a);
                Push(valuestack, num);
            }
            switch(*s.base)
            {
                case '+':
                    num1 = Top(valuestack);
                    Pop(valuestack);
                    num2 = Top(valuestack);
                    Pop(valuestack);
                    num = num2 + num1;
                    Push(valuestack, num);
                    break;
                case '-':
                    num1 = Top(valuestack);
                    Pop(valuestack);
                    num2 = Top(valuestack);
                    Pop(valuestack);
                    num = num2 - num1;
                    Push(valuestack, num);
                    break;
                case '*':
                    num1 = Top(valuestack);
                    Pop(valuestack);
                    num2 = Top(valuestack);
                    Pop(valuestack);
                    num = num2 * num1;
                    Push(valuestack, num);
                    break;
                case '/':
                    num1 = Top(valuestack);
                    Pop(valuestack);
                    num2 = Top(valuestack);
                    Pop(valuestack);
                    num = num2 / num1;
                    Push(valuestack, num);
            }
            s.base++;
        }
        value = Top(valuestack);
        return value;
    }
    
    
    //主函数
    int main()
    {
        int i;
        //初始化栈
        InitSqstack(temporarystack);
        InitSqstack(resultstack);
        cout << "输入表达式:";
        for(i = 0; i <= 100; i++)
        {
            cin >> s[i];
            if('=' == s[i])
            {
                s[i + 1] = '\0';
                break;
            }
        }
        TransformReversePolish(s);
        cout << "逆波兰表达式为:";
        PrintSqstack(resultstack);
        Pop(resultstack);
        cout << endl;
        cout << "计算结果:";
        cout << Calculate(resultstack) << endl;
        system("pause");
        return 0;
    }

运行结果：

![70][]

总结下：

应该计算没有太大的问题，就是中缀转逆波兰表达式的算法比较烂，我也懒得优化了，，，等有时间再说吧。

如果发现计算结果有问题可以在下面评论。。。

对了顺便说下如何输入：输入任意表达式，可以包含小数，加减乘除括号（英文状态下的括号哦），以等号符结束程序。

emmm，就这样吧，谢谢！

[70]: /images/20220523/8a9f736884ad4b3980c307a727074a60.png