利用栈计算算数表达式的值

先将中缀表达式利用栈转换为后缀表达式，然后再利用栈由后缀表达式计算算数表达式的值，具体代码如下：

#include using namespace std;#include #include #include enum Type{        OP_NUM,        OP_SYMBOL,};enum Operat{        ADD,        SUB,        MUL,        DIV,};struct Cell{        Type _type;        int _num;};//input = 1 + ((2 + 3) * 4) - 5;//中缀到后缀string topolishNotation(const char* input){        stack s1; //运算符        stack s2; //数字        size_t iCount = 0;        while (input[iCount] != '\0')        {                //是数字将其压入s2                if (input[iCount] >= '0'&& input[iCount] <= '9')                {                        while (input[iCount] != '\0' && input[iCount] >= '0'&& input[iCount] <= '9')                        {                                s2.push(input[iCount++]);                        }                        s2.push(' ');                        --iCount; //最后会统一加1，所以先减一                }                //是运算符比较其与S1栈顶运算符的优先级                while (input[iCount] == '+' || input[iCount] == '-' ||                        input[iCount] == '*' || input[iCount] == '/')                {                        //s1为空，或栈顶运算符为左括号"("，则直接将此运算符入栈                        if (s1.empty() || s1.top() == '(')                        {                                s1.push(input[iCount]);                                break;                        }                        //否则，若优先级比栈顶运算符的高，也将运算符压入s1                        else if ((input[iCount] == '*' || input[iCount] == '/') &&                                (s1.top() == '+' || s1.top() == '-'))                        {                                s1.push(input[iCount]);                                break;                        }                        //否则，将S1栈顶的运算符弹出并压入到S2中，再次与S1中新的栈顶运算符相比较                        else                        {                                s2.push(s1.top());                                s1.pop();                        }                }                //如果是左括号"("，则直接压入S1；                if (input[iCount] == '(')                {                        s1.push(input[iCount]);                }                /*如果是右括号")"，则依次弹出S1栈顶的运算符，并压入S2，                *直到遇到左括号为止，此时将这一对括号丢弃；*/                if (input[iCount] == ')')                {                        while (s1.top() != '(')                        {                                s2.push(s1.top());                                s1.pop();                        }                        s1.pop(); //将'('也出栈                }                ++iCount; //统一加一次        }        //将S1中剩余的运算符依次弹出并压入S2；        while (!s1.empty())        {                s2.push(s1.top());                s1.pop();        }        string ret;        while (!s2.empty())        {                ret.push_back(s2.top());                s2.pop();        }        reverse(ret.begin(), ret.end());        return ret;}//后缀到数组vector StrBehindToVect(const string& strBehind){        vector call;        size_t iCount = 0;        while (strBehind[iCount] != '\0')        {                if (strBehind[iCount] >= '0' && strBehind[iCount] <= '9')                {                        int ret = 0;                        while (strBehind[iCount] != '\0' && strBehind[iCount] >= '0' && strBehind[iCount] <= '9')                        {                                ret = ret * 10 + strBehind[iCount] - '0';                                ++iCount;                        }                        call.push_back({ OP_NUM, ret });                        --iCount;                }                else if (strBehind[iCount] == '+')                {                        call.push_back({ OP_SYMBOL, ADD });                }                else if (strBehind[iCount] == '-')                {                        call.push_back({ OP_SYMBOL, SUB });                }                else if (strBehind[iCount] == '*')                {                        call.push_back({ OP_SYMBOL, MUL });                }                else if (strBehind[iCount] == '/')                {                        call.push_back({ OP_SYMBOL, DIV });                }                ++iCount;        }        return call;}//计算值int RPNCount(const vector& array, size_t size){        stack val;        for (size_t i = 0; i < size; ++i)        {                if (array[i]._type == OP_NUM)                {                        val.push(array[i]._num);                }                else                {                        int right = val.top();                        val.pop();                        switch (array[i]._num)                        {                        case ADD:                                val.top() += right;                                break;                        case SUB:                                val.top() -= right;                                break;                        case MUL:                                val.top() *= right;                                break;                        case DIV:                                if (right == 0)                                {                                        throw(array[i]);                                }                                val.top() /= right;                                break;                        default:                                cout << "请输入合法字符" << endl;                                exit(0);                        }/*switch*/                }        }        return val.top();}int main(){        string strMid = "12 * (3 + 4) - 6 + 8 / 2";        string strBehind = topolishNotation(strMid.c_str());        vector call = StrBehindToVect(strBehind);        try        {                int ret = RPNCount(call, call.size());                cout << ret << endl;        }        catch (Cell)        {                cout << "除数为0!" << endl;        }        system("pause");        return 0;}