首页 > 代码库 > C++与数据结构 -- stack实现表达式求值[注释版]

C++与数据结构 -- stack实现表达式求值[注释版]

    有好多朋友评论以前的那篇博文说:代码中间没有注释。由于课程一直比较紧张,所以答应的注释直到今天才写,

发表出来,与大家共享!

#include <map>
#include <stack>
#include <string>
#include <iostream>
#include <fstream>
using namespace std;

//为+,-,*,/运算符 设定优先级
map<char,int> priority;
void initMap()
{
    //+,-运算符的优先级低于*,/
    priority.insert(make_pair(‘+‘,1));
    priority.insert(make_pair(‘-‘,1));
    priority.insert(make_pair(‘*‘,2));
    priority.insert(make_pair(‘/‘,2));
}

//为特定的运算符进行计算
int calculate(int a,char opera,int b)
{
    int res = 0;
    switch(opera)
    {
    case ‘-‘:
        res = a - b;
        break;
    case ‘+‘:
        res = a + b;
        break;
    case ‘*‘:
        res = a * b;
        break;
    case ‘/‘:
        res = a / b;
    }

    return res;
}

//中缀表达式转后缀表达式
string infixToSuffix(const string &str)
{
    stack<char> charStack;
    string ans; //返回值

    for (string::const_iterator iter = str.begin(); iter != str.end(); ++iter)
    {
        if (isdigit(*iter)) //如果是数字,则直接输出[实际上是将其压入返回值]
        {
            ans.push_back(*iter);
        }
        else
        {
            //如果字符栈为空,或该字符为"(",或该运算符的优先级高于或等于栈顶元素,则进栈
            if (charStack.empty() || *iter == ‘(‘ || priority[*iter] >= priority[charStack.top()])
            {
                charStack.push(*iter);
            }
            //如果该字符为")",则将字符栈中的元素输出[放入到ans中],直到遇到"("为止
            else if (*iter == ‘)‘)
            {
                while (charStack.top() != ‘(‘)
                {
                    ans.push_back(charStack.top());
                    charStack.pop();
                }
                charStack.pop();    //将栈顶的"("弹出
            }
            //如果该运算符的优先级低于栈顶元素,则将栈中运算符持续输出,
            //直到遇到比该运算符优先级低的运算符为止
            else if (priority[*iter] < priority[charStack.top()])
            {
                while (!charStack.empty() && priority[charStack.top()] >= priority[*iter])
                {
                    ans.push_back(charStack.top());
                    charStack.pop();
                }
                charStack.push(*iter);  //将该运算符入栈
            }
        }
    }
    //将栈中所剩余的运算符持续输出
    while (!charStack.empty())
    {
        ans.push_back(charStack.top());
        charStack.pop();
    }

    return ans;
}

//后缀表达式求值
int figureOut(const string &expr)
{
    stack<int> intStack;

    for (string::const_iterator iter = expr.begin(); iter != expr.end(); ++iter)
    {
        //如果该元素为数字,则直接进入数字栈
        if (isdigit(*iter))
        {
            intStack.push((*iter - ‘0‘));
        }
        //如果该元素是运算符,则将栈顶的两个元素取出,进行计算,将结果压入数字栈
        else
        {
            char o = *iter;

            int a = intStack.top(); //取出栈顶元素
            intStack.pop(); //删除栈顶元素

            int b = intStack.top(); //取出栈顶元素
            intStack.pop(); //删除栈顶元素

            intStack.push(calculate(b,o,a));    //计算并入栈
        }
    }

    return intStack.top();  //返回最终结果
}

int main()
{
//  freopen("input.txt","r",stdin);

    initMap();  //初始化运算符优先级

    string expr;    //中缀表达式
    while (cin >> expr)
    {
        string suffix = infixToSuffix(expr);    //后缀表达式
//删除栈顶元素
        int ans = figureOut(suffix);
        cout << ans << endl;
    }
}

/**测试数据:
* 9+8/4*(2+1)/2
* 9+(3-1)*3+8/2

**注意:该程序只能处理表达式中的数字只能为0~9,
*       大于个位的数字无法处理!
*/