逆波兰表示

逆波兰表达式

一篇很好的文章
表达式一般由操作数(Operand)、运算符(Operator)组成，例如算术表达式中，通常把运算符放在两个操作数的中间，这称为中缀表达式(Infix Expression)，如A+B。

波兰数学家Jan Lukasiewicz提出了另一种数学表示法，它有两种表示形式：
把运算符写在操作数之前，称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression)，如+AB；

把运算符写在操作数之后，称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression)，如AB+；

其中，逆波兰表达式在编译技术中有着普遍的应用。
逆波兰表达式是一种后缀表达式，不同与我们常见的中缀表达式。

逆波兰记法中，操作符置于操作数的后面。例如表达“三加四”时，写作“3 4 +”，而不是“3 + 4”。如果有多个操作符，操作符置于第二个操作数的后面，所以常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5 +”：先3减去4，再加上5。使用逆波兰记法的一个好处是不需要使用括号。例如中缀记法中“3 - 4 5”与“（3 - 4）5”不相同，但后缀记法中前者写做“3 4 5 -”，无歧义地表示“3 (4 5 ) −”；后者写做“3 4 - 5 *”。
逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是：操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；当一遍后，栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现，和能很快求值。
注意：逆波兰记法并不是简单的波兰表达式的反转。因为对于不满足交换律的操作符，它的操作数写法仍然是常规顺序，如，波兰记法“/ 6 3”的逆波兰记法是“6 3 /”而不是“3 6 /”；数字的数位写法也是常规顺序。 —wiki

将中缀表达式转换为后缀表达式(后缀表达式)

算法思路:
(1)首先，需要分配2个栈，栈s1用于临时存储运算符（含一个结束符号），此运算符在栈内遵循越往栈顶优先级越高的原则；栈s2用于输入逆波兰式，为方便起见，栈s1需先放入一个优先级最低的运算符，在这里假定为’#’；
(2)从中缀式的左端开始逐个读取字符x，逐序进行如下步骤：
1.若x是操作数，则分析出完整的运算数（在这里为方便，用字母代替数字），将x直接压入栈s2；(这里最好用空格将数与数之间隔开，数与运算符之间)
2.若x是运算符，则分情况讨论：
若x是’(‘，则直接压入栈s1；
若x是’)’，则将距离栈s1栈顶的最近的’(‘之间的运算符，逐个出栈，依次压入栈s2，此时抛弃’(‘；
若x是除’(‘和’)’外的运算符，则再分如下情况讨论：
若当前栈s1的栈顶元素为’(‘，则将x直接压入栈s1；
若当前栈s1的栈顶元素不为’(‘，则将x与栈s1的栈顶元素比较，若x的优先级大于栈s1栈顶运算符优先级，则将x直接压入栈s1。否者，将栈s1的栈顶运算符弹出，压入栈s2中，直到栈s1的栈顶运算符优先级别低于（不包括等于）x的优先级，或栈s2的栈顶运算符为’(‘，此时再则将x压入栈s1;
(3)在进行完(2)后，检查栈s1是否为空，若不为空，则将栈中元素依次弹出并压入栈s2中（不包括’#’）；　　　　　　
(4)完成上述步骤后，栈s2便为逆波兰式输出结果。但是栈s2应做一下逆序处理，因为此时表达式的首字符位于栈底；

具体实现请看
代码

计算逆波兰式的结果

150. Evaluate Reverse Polish Notation
根据给出的逆波兰表达式，求出相应的计算式的值
(1)取出当前的字符

如果是数，则则直接入栈
如果是运算符，那么就取出位于栈顶的元素进行运算，并将结果压入栈中
栈中只有一个数，就是最终的结果

中缀表达式“5 + ((1 + 2) 4) − 3”写作
5 1 2 + 4 + 3 −
下表给出了该逆波兰表达式从左至右求值的过程，堆栈栏给出了中间值，用于跟踪算法。
|输入| 操作| 堆栈| 注释|
|:—|:—|:—|:—|
|5| 入栈| 5|
|1| 入栈| 5, 1|
|2| 入栈| 5, 1, 2|
|+| 加法运算| 5, 3| (1, 2)出栈；将结果（3）入栈|
|4| 入栈| 5, 3, 4|
|*| 乘法运算| 5, 12| (3, 4)出栈；将结果（12）入栈|
|+| 加法运算| 17| (5, 12)出栈；将结果 (17)入栈|
|3| 入栈| 17, 3|
|−| 减法运算| 14| (17, 3)出栈；将结果（14）入栈|

计算完成时，栈内只有一个操作数，这就是表达式的结果：14

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
    
        for(int i = 0; i != tokens.size(); ++i){
            if( isNumber(tokens[i]) )
                st.push(stoi(tokens[i]));
            else if(tokens[i] == "+"){
                int val2 = st.top(); st.pop();
                int val1 = st.top(); st.pop();
                
                st.push(val1+val2);
            }
            else if(tokens[i] == "*"){
                int val2 = st.top(); st.pop();
                int val1 = st.top(); st.pop();
                
                st.push(val1 * val2);
            }
            else if(tokens[i] == "-"){
                int val2 = st.top(); st.pop();
                int val1 = st.top(); st.pop();
                
                st.push(val1 - val2);
            }else if(tokens[i] == "/"){
                int val2 = st.top(); st.pop();
                int val1 = st.top(); st.pop();
                if(val2 == 0)
                    printf("zero divided\n");
                else
                    st.push(val1 / val2);
            }else{
                printf("invalid token\n");
            }
        }
        return st.top();
    }
    
    int isNumber(string &s){
        int i;
        
        for(i = 0; i != s.size()&& isspace(s[i]); ++i)
            ;
        if(s[i] == '+' || s[i] == '-')
            ++i;
        return isdigit(s[i]);
    }
};

中缀表达式转换成前缀表达式

这里会倒序遍历输入的字符串(转换成后缀的时候是顺序嘞)
中缀表达式转换成前缀表达式和中缀表达式转换成后缀表达式十分类似，只需要将扫描方向由前往后变成由后往前，
将’(‘改为’)’,’)’改为’(‘,注意其中一个判断优先级的地方需要由>=变成>