【Algorithm#0x00】数据结构-逆波兰表示法

四则运算表达式求值 - 逆波兰表示法

逆波兰表示法是栈结构的典型应用。
在逆波兰表示法中，无论是“把中缀表达式转化成后缀表达式”，还是“计算后缀表达式”，都需要用栈作为工具。
所以我写了一个简单的表达式转换程序试了下……（仅支持个位数加减法）

#include <iostream>
#include <string>
#include <stack>
#include <cctype>
using namespace std;

// 返回符号优先级，若非运算符则返回0
inline unsigned short prior(char c)
{
    switch (c)
    {
        case '*':
        case '/':
            return 2;
        case '+':
        case '-':
            return 1;
        default:
            return 0;
    }
}

// 将中缀表达式a转化为后缀表达式，并存储在c中
void convert_expression(string& a, string& c)
{
    stack<char> b;

    for (int i = 0; i < a.length(); ++i)
    {
        // 数字直接输出
        if (('0'<=a[i] && a[i]<='9'))
        {
            c.push_back(a[i]);
            continue;
        }
        // 左括号直接压栈
        else if (a[i] == '(')
        {
            b.push(a[i]);
        }
        // 右扩号则循环输出直到左括号
        else if (a[i]==')')
        {
            while (b.top() != '(')
            {
                c.push_back(b.top());
                b.pop();
            }
            b.pop();
            continue;
        }
        // 处理符号优先级
        else if (prior(a[i]))
        {
            // 当前符号优先级 <= 栈顶符号优先级：栈顶符号出栈
            while (!b.empty() && prior(a[i]) <= prior(b.top()))
            {
                c.push_back(b.top());
                b.pop();
            }
            b.push(a[i]);
        }
        // 处理非法字符
        else
        {
            cout << "Please check your expression." << endl;
        }
    }
    // 输出栈内剩余字符
    while (!b.empty())
    {
        c.push_back(b.top());
        b.pop();
    }
}

int main(void)
{
    string expression;  cin >> expression;
    string postfix_expression;
    convert_expression(expression, postfix_expression);
    cout << postfix_expression << endl;
}