中缀表达式:(或中缀记法)是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的算术表示方法。(取自百度百科)

后缀表达式:缀表达式,又称逆波兰式,指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。(取自百度百科)

蓝桥杯培训时有一道模拟手算的题,用的就是这种思路,之前稍微了解了下就没管了。这学期学数据结构书上提到了,并且老师叫我们写的题目上也有类似的题目。于是今天就照着书上的思路把它给拿下了,等会再去把蓝桥那道拿下!

原题

AC代码如下:

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{
    stack<char> t;
    string s;
    string res;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '+' || s[i] == '-')
        {
            while (!t.empty() && t.top() != '(')
            {
                res.append(1, t.top());
                t.pop();
            }
            t.push(s[i]);
        }
        else if (s[i] == '*' || s[i] == '/')
        {
            while (!t.empty() && t.top() != '('  && t.top() != '+' && t.top() != '-')
            {
                res.append(1, t.top());
                t.pop();
            }
            t.push(s[i]);
        }
        else if (s[i] == '(')
        {
            t.push(s[i]);
        }
        else if (s[i] == ')')
        {
            while (t.top() != '(')
            {
                res.append(1, t.top());
                t.pop();
            }
            t.pop(); // 将(出栈
        }
        else
        {
            res.append(1, s[i]);
        }
    }

    while (!t.empty())
    {
        res.append(1, t.top());
        t.pop();
    }
    cout << res << endl;

    return 0;
}

思路直接copy书上的了:
思路

最后修改:2019 年 03 月 07 日 04 : 45 PM
如果觉得我的文章对你有用,请随意赞赏