程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 利用兩個棧求解算數表達式的源代碼

利用兩個棧求解算數表達式的源代碼

編輯：C++入門知識

說明：
1、只包含了小括號（），和+、-、*、/二元操作符的四則運算
2、求它更通用的求解方法可以參考遞歸求解、通過表達式樹求解的方法

[cpp]
#include <cctype>
#include <map>
#include <stack>
#include <string>
#include <iostream>

using namespace std;

//彈出操作符棧的一個操作符，彈出操作數棧的一個操作數，計算結果
void Compute(stack<char> &operators, stack<double> &operands)
{
    double op2 = operands.top();
    operands.pop();
    double op1 = operands.top();
    operands.pop();
    char optr = operators.top();
    double result;
    switch(optr)
    {
    case '+':
        result = op1 + op2;
    case '-':
        result = op1 - op2;
    case '*':
        result = op1 * op2;
    case '/':
        result = op1 / op2;
    }
    operands.push(result);
    operators.pop();
}

//通過操作符棧和操作數棧求解表達式，表達式正確返回true，結果存在result裡，錯誤返回false
bool ComputeExpr(const string &expr, map<char,int> &priority_tbl, double &result)
{
    stack<double> operands;//操作數棧
    stack<char> operators;//操作符棧

    string inner_expr(expr + '$');//加個哨兵
    operators.push('#');//哨兵

    for(int i = 0; i < inner_expr.length(); ++i)
    {
        char ch = inner_expr[i];
        if(isdigit(ch))//操作數直接入操作數棧
            operands.push(ch - 0x30);
        else//操作符
        {
            switch(ch)
            {
            case '(':
                operators.push(ch);
                break;
            case ')': //求解當前最內部的括號表達式
                while(operators.top() != '(')
                {
                    if(operators.top() == '#' || operands.size() < 2)
                        return false;
                    Compute(operators, operands);
                }
                operators.pop();
                break;
            case '$': //此時，正確表達式已經不存在括號了，計算
                while(operators.top() != '#')
                {
                    if(operands.size() < 2)
                        return false;
                    Compute(operators, operands);
                }
                if(operands.size() == 1)
                {
                    result = operands.top();
                    return true;
                }
                return false;
            default: //一般的二元操作符求解
                while(priority_tbl[ch] <= priority_tbl[operators.top()])
                {
                    if(operands.size() < 2)
                        return false;
                    Compute(operators, operands);
                }
                operators.push(ch);
            }
        }
    }
}

int main(int argc, char *argv[])
{
    const string expr_str("((5+6)*7/(2-9)*9)+5");

    //優先級表，數字越大，優先級越高
    map<char, int> priority_tbl;
    priority_tbl.insert(make_pair('+',2));
    priority_tbl.insert(make_pair('-',2));
    priority_tbl.insert(make_pair('*',3));
    priority_tbl.insert(make_pair('/',3));
    priority_tbl.insert(make_pair('(',1));
    priority_tbl.insert(make_pair('#',0));

    double result;

    bool ret = ComputeExpr(expr_str, priority_tbl, result);

    if(ret)
    {
        cout << expr_str << " = " << result << endl;
    }
    else
    {
        cout << "表達式錯誤！" << endl;
    }

    return 0;
}