逆波兰表达式C++代码实现

￡神魔★判官ぃ 2022-08-09 13:50 166阅读 0赞

当我们输入一个数学表达式，是中缀表达式，我们首先转换为后缀表达式（逆波兰表达式），然后再进行求值。

在《大话数据结构》的104-100页有详细的介绍，下面是我理解之后的代码实现。

代码思路：

（1）首先对输入的中缀表达式合法性进行判断，bool isStringLegal(const char\* str); 函数实现。

（2）然后把中缀表达式转换为后缀表达式。

（3）根据后缀表达式求出结果，double getTheResult(vector<string> &vec);函数实现。

注意：表达式的运算符可以输入 加、减、乘、除、括号，输入的数据为整形数据，计算结果为double型数据。

#include <iostream>
    #include <math.h>
    #include <map>
    #include <vector>
    #include <string.h>
    #include <memory>
    #include <string>
    #include <stdio.h>
    #include <stack>
    #include <stdlib.h>
    
    using namespace std;
    
    #define MAX_STRING_LENGTH 100
    
    /* 解析当前的整形数据，并把整形数据转换为string型 */
    string analyData(const char* str, int &i);
    
    /* 根据逆波兰表达式求表达式的值 */
    double getTheResult(vector<string> &vec);
    
    /* 判断该字符是否是 + - * / ( ) */
    bool isCalChar(const char ch);
    
    /* 判断输入的中缀表达式是否合法 */
    bool isStringLegal(const char* str);
    
    
    
    /* 解析当前的整形数据，并把整形数据转换为string型 */
    string analyData(const char* str, int &i)
    {
        int temp = i++;
        while(str[i] >= '0' && str[i] <= '9' && str[i] != '\0')
        {
            i++;
        }
    
        string s(str+temp,str+i);
    
        return s;
    }
    
    /* 根据逆波兰表达式求表达式的值 */
    double getTheResult(vector<string> &vec)
    {
        vector<string>::iterator it;
        stack<double> sta;
    
        string strTemp;
        double d = 0, d1 = 0, d2 = 0;
    
        for(it = vec.begin(); it != vec.end(); it++)
        {
            strTemp = (*it);
    
            if(strTemp == "+")
            {
                d1 = sta.top();
                sta.pop();
    
                d2 = sta.top();
                sta.pop();
    
                d = d1 + d2;
                sta.push(d);
            }
            else if(strTemp == "-")
            {
                d1 = sta.top();
                sta.pop();
    
                d2 = sta.top();
                sta.pop();
    
                d = d2 - d1;
                sta.push(d);
            }
            else if(strTemp == "*")
            {
                d1 = sta.top();
                sta.pop();
    
                d2 = sta.top();
                sta.pop();
    
                d = d2 * d1;
                sta.push(d);
            }
            else if(strTemp == "/")
            {
                d1 = sta.top();
                sta.pop();
    
                d2 = sta.top();
                sta.pop();
    
                d = d2 / d1;
                sta.push(d);
            }
            else
            {
                const char *p = strTemp.c_str();
                d = atoi(p);
                sta.push(d);
            }
        }
        return sta.top();
    }
    
    /* 判断该字符是否是 + - * / ( ) */
    bool isCalChar(const char ch)
    {
        if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '('  || ch == ')')
        {
            return true;
        }
    
        return false;
    }
    /* 判断输入的中缀表达式是否合法 */
    bool isStringLegal(const char* str)
    {
        /* 判断是否是空串 */
        if(NULL == str)
        {
            return false;
        }
    
        int len = strlen(str);
        int i = 0;
        int flag = 0;
    
        /* 字符串的开头和末尾是否是数字 */
        if(str[0] > '9' || str[0] < '0' || str[len-1] > '9' || str[len-1] < '0')
        {
            return false;
        }
    
    
        for(i = 0; str[i] != '\0'; i++)
        {
            /* 是否有除了加减乘除括号之外的字符 */
            if(isCalChar(str[i]) == false)
            {
                return false;
            }
    
            /* 判断是否有两个连续的符号 */
            if(i < len-1 && isCalChar(str[i]) == true)
            {
                if(isCalChar(str[i+1]) == true)
                {
                    return false;
                }
    
            }
    
            /* 判断括号是否成对 */
            if(str[i] == '(')
            {
                flag++;
            }
            else if(str[i] == ')')
            {
                flag--;
            }
    
            /* 判断是否出现 )( 这样的情况 */
            if(flag < 0)
            {
                return false;
            }
        }
    
        /* 判断括号是否匹配 */
        if(flag != 0)
        {
            return false;
        }
    
        return true;
    }
    
    int main(void)
    {
        char str[MAX_STRING_LENGTH] = {0};
        int i = 0;
        string data;
    
        /* 存放运算符表达式的栈 */
        stack<char> oper_char;
    
        /* 存放后缀表达式 */
        vector<string> post_str;
    
        /* 输入中缀的表达式 */
        gets(str);
    
        /* 判断输入的中缀表达式是否合法 */
        if(isStringLegal(str) != true)
        {
            cout << "This expression is not legal." << endl;
        }
        else
        {
            /* 将中缀表达式转换为后缀表达式 */
            for(i = 0; str[i] != '\0'; i++)
            {
                /* 如果该字符为数字,解析该数字，并压入栈 */
                if(str[i] >= '0' && str[i] <= '9')
                {
                    data = analyData(str,i);
                    post_str.push_back(data);
                    i--;
                }
                else if(str[i] == '(')
                {
                    oper_char.push(str[i]);
                }
                else if(str[i] == ')')
                {
                    char chtemp[2] = {0};
    
                    chtemp[0] = oper_char.top();
    
                    while(chtemp[0] != '(')
                    {
                        string strtemp(chtemp);
                        post_str.push_back(strtemp);
                        oper_char.pop();
    
                        chtemp[0] = oper_char.top();
                    }
                    oper_char.pop();
                }
                else if(str[i] == '+' || str[i] == '-')
                {
                    char chtemp[2] = {0};
    
                    /* 全部出栈，但是碰到 '('就要停止出栈 */
                    while(oper_char.size() != 0)
                    {
                        chtemp[0] = oper_char.top();
                        if(chtemp[0] == '(')
                        {
                            break;
                        }
    
                        oper_char.pop();
    
                        string strtemp(chtemp);
                        post_str.push_back(strtemp);
                    }
    
                    /*将当前的表达式符号入栈*/
                    oper_char.push(str[i]);
                }
                else if(str[i] == '*' || str[i] == '/')
                {
                    char chtemp[2] = {0};
                    while(oper_char.size() != 0)
                    {
                        chtemp[0] = oper_char.top();
                        if(chtemp[0] == '(' || chtemp[0] == '+' || chtemp[0] == '-')
                        {
                            break;
                        }
                        else
                        {
                            oper_char.pop();
    
                            string strtemp(chtemp);
                            post_str.push_back(strtemp);
                        }
                    }
    
                    /*将当前的表达式符号入栈*/
                    oper_char.push(str[i]);
                }
            }
    
            /* 存放表达式的栈可能还有数据 */
            while(!oper_char.empty())
            {
                char chtemp[2] = {0};
                chtemp[0] = oper_char.top();
                oper_char.pop();
    
                string strtemp(chtemp);
                post_str.push_back(strtemp);
            }
    
            /* 把逆波兰表达式求值 */
            cout << getTheResult(post_str) << endl;
        }
    
        return 0;
    }