逆波兰表达式

我们一般使用的算数表达式都是中缀表达式，我们可以很容易的理解其中的逻辑计算次序，但是这对于计算器来说就很难理解了，于是就出现了逆波兰表达式，也称为后缀表达式，有了这个表达式，现代计算器就能实现多部计算了。

中缀表达式：
** 9+（3-1）3+10/2*
对应形式的后缀表达式：
9 3 1 - 3 * + 10 2 / +

我们将一个中缀表达式转换成后缀表达式之后，我们就可以利用一个栈将结果求出，以上式为例：
我们先定义规则：从左至右依次读取，遇见数字，将数字压栈，遇见符号，将栈顶弹出两次，将弹出的两个数字进行运算，之后再将此数字入栈，一直到后缀表达式计算完毕。

首先，我们将9压栈，之后是3和1，没有遇到符号也压栈，之后遇到了‘-’号，我们就将3和1弹出，计算3-1=2，之后将2压栈，之后碰到‘*’号，我们就将栈中的9，2弹出，计算9*2=18，将18压栈，之后是3，压栈，‘-’号，出栈计算18-3=15，压栈，10与2压栈，‘/’号，计算10/2=5，压栈，最后栈中剩下15与5，最后的符号为‘+’号，我们计算最后一步，15+5=20，20就是我们最后得出的结果。

这样，利用了后缀表达式，我们就将一个中缀计算式改写成为可以按照从左向右读取的顺序来计算的式子了，这对于只能顺序读取的CPU来说是个很好的消息。

那么，我们如何将一个中缀表达式改写成为对应的后缀表达式呢？以上式为例，我们同样用到了栈：
我们先定义规则：从左至右依次读取，遇见数字就输出，遇见符号（如果是‘（’，直接入栈）就先判断与其栈顶符号的优先级，若是‘）’，或优先级小于栈顶符号，则栈顶元素依次出栈，直到遇见‘（’，或全部弹出，之后再将当前符号入栈（‘）’不需要入栈），一直到中缀表达式输入完毕，若符号栈中还存有符号，依次弹出。

首先，9输出，‘+’号入栈，‘（’入栈，3输出，‘-’号入栈，1输出，之后碰到‘）’，将符号栈弹出，直到‘（’，即‘-’号出栈，此时栈中元素为‘+’，输出的后缀表达式为9 3 1 -，之后‘*’号，判断与栈顶元素（‘+’）的优先级，入栈，3输出，‘+’号，判断（‘*’），优先级小，栈顶元素依次弹出至空栈，即‘*’号出栈，‘+’号出栈，再将这个‘+’号入栈，此时栈中元素为‘+’，输出的后缀表达式为9 3 1 - 3 * +，之后10输出，‘/’号，判断（‘+’），入栈，2输出，中缀表达式输出完毕，依次将符号栈清空，‘/’号弹出，‘+’号弹出，最后我们得到的后缀表达式就为9 3 1 - 3 * + 10 2 / +。

具体代码实现（本人实力有限，代码可能不是特别好看，见谅）：

//使用C++实现后缀表达式
//输入一个string，返回vector<string>形式的后缀表达式
//没有处理分数形式，没有检测输入错误能力

#include <iostream>
#include <string>
#include <vector>
#include <cctype>

using namespace std;

struct charStack         //定义符号栈
{
    char ch[100];
    int cur;
};

char curStackTop(charStack& stack)       //返回当前的栈顶元素
{
    return stack.ch[stack.cur];
}

void pushStack(charStack& stack,char ch)    //将符号压栈
{
    stack.cur++;
    stack.ch[stack.cur] = ch;
}

char popStack(charStack& stack)       //弹栈
{
    stack.cur--;
    return stack.ch[stack.cur+1];
}

bool canPopStack(charStack& stack,char ch)     //判断是否可以弹出栈顶
{
    if(stack.cur == -1 || ch == '(')             //如果是空栈或‘（’，不能弹出
    {
        return false;
    }
    int levelStack,levelCh;                      //定义栈顶元素和当前元素的优先级
    if(ch == '+'||ch == '-')                   //‘-’，‘+’优先级低
    {
        levelCh = 0;
    }
    else
    {
        levelCh = 1;
    }
    if(stack.ch[stack.cur] == '+' || stack.ch[stack.cur] == '-' || stack.ch[stack.cur] == '(')                 
    {
    //由于栈顶元素可能是‘（’，而‘（’要读到‘）’才弹出，所以定义优先级低
        levelStack = 0;
    }
    else
    {
        levelStack = 1;
    }
    if(levelCh < levelStack)
    {
        return true;
    }
    else
    {
        return false;
    }
}

charStack& initStack(charStack& stack)   //初始化栈
{
    stack.cur = -1;
    return stack;
}

vector<string> getStringList(const string& str)   //将输入的string按照数字，符号切割开来
{                                                   
    vector<string> vec;
    string temp;                //临时存储数据
    bool flag;                    //判断数字是否结束
    for(auto c : str)
    {
        if(c <= '9' && c >= '0')
        {
            temp.push_back(c);
            flag = true;
        }
        else
        {
            if(flag)
            {
                vec.push_back(temp);
                flag = false;
                temp.clear();
            }
            temp.push_back(c);
            vec.push_back(temp);
            temp.clear();
        }
    }
    if(!temp.empty())
    {
        vec.push_back(temp);
    }
    return vec;
}

vector<string> toRPN(vector<string>& vec)    //将vector<string>转换成后缀表达式
{
    vector<string> vec_RPN;         //存储后缀表达式的容器
    charStack stack;                  //定义符号栈
    stack = initStack(stack);
    string temp;
    for(auto c : vec)
    {
        if(isdigit(c.at(0)))                    //如果是数字，直接压栈
        {
            vec_RPN.push_back(c);
        }
        else
        {
            if(c.at(0) == ')' || canPopStack(stack,c.at(0)))     //是符号，判断优先级与是否是‘）’
            {
                while(curStackTop(stack) != '(' && stack.cur != -1)       //弹出元素，直到空栈或‘（’
                {
                    temp.push_back(popStack(stack));
                    vec_RPN.push_back(temp);
                    temp.clear();
                }
                if(curStackTop(stack) == '(' && c.at(0) == ')')  //当前符号是‘）’，则将栈顶元素‘（’弹出
                {
                    popStack(stack);
                }
                if(c.at(0) != ')')                     //如果不是‘）’，将当前元素压栈
                {
                    pushStack(stack,c.at(0));
                }
            }
            else
            {
                pushStack(stack,c.at(0));            //优先级大，直接压栈
            }
        }
    }
    while(stack.cur != -1)                //将最后的栈清空
    {
        temp.push_back(popStack(stack));
        vec_RPN.push_back(temp);
        temp.clear();
    }
    return vec_RPN;             //返回后缀表达式，类型为vector<string>
}

这就是实现中缀表达式转后缀表达式的方法，至于如何将后缀表达进行计算，我想能利用栈完成转换的人都可以利用栈将后缀表达式的结果计算出来。