数据结构之逆波兰表达式

所谓逆波兰便是反其道而行之.我们一般上的表达式,运算符都是镶嵌在数与数之间的,而逆波兰则独树一帜将运算变成了小尾巴粘到了数字的后面.说起来好像很抽象,还是举个例子吧.
例:

该表达式的运算顺序:

1. b - c = x
2. x * d = y
3. a + y = z
4. z / e = result
   逆波兰采用了栈的先进后出的方式罗列数字与运算符的顺序
   第一步将a压入栈中,第二步将b压入,第三步压入c
   在压入运算符" - “的时候,
   数字便会按照压入栈中的逆序弹出,
   先弹出c然后再弹出b,
   再将拿到的b减去c得到X.
   接着又将X压入栈中,
   然后把d也压入栈中,
   遇到运算符” * “,
   同理弹出d和X,
   再将X乘以d得到Y,
   将Y压入,
   遇到” + “,
   弹出Y, a,
   a + y = Z,
   压入Z,
   压入e,
   遇到” / ",
   弹出e , Z
   Z / e = result
   
   
   
   
   
   努力做得详细一些,希望你能看懂.
   接下来是实现的代码:

public class Test{
    public static void main(String[] args){
        String[] notation = {"3", "15", "24", "+", "/", "4", "9", "*", "-"};
        int result = ReversePolishNotation.caculate(notation);
        System.out.println(result);		
    }
}
public static class ReversePolishNotation{
    public static int caculate(String[] notation){
        Stack<Integer> oprands = new Stack<>();
        for(String operator : notation){
            Integer numF;
            Integer numS;
            switch(operator){
                case "+" :
	                    numF = oprands.pop();
	            		numS = oprands.pop();
	                    result = numS + numF;
	                    oprands.push(result);
	                    break;
                case "-" :
	                    numF = oprands.pop();
	            		numS = oprands.pop();
	                    result = numS - numF;
	                    oprands.push(result);
	                    break;
                case "*" :
	                    numF = oprands.pop();
	            		numS = oprands.pop();
	                    result = numS * numF;
	                    oprands.push(result);
	                    break;
                case "/" :
	                    numF = oprands.pop();
	            		numS = oprands.pop();
	                    result = numS / numF;
	                    oprands.push(result);
	                    break;
                default:
                    oprands.push(Integer.parseInt(result));
                    break;
            }
        }
        int result = oprands.pop();
        return result;
    }
}

随便写了些数字我的结果是负数,但是是正确的,你也可以测测看.
白嫖很香,不用客气,请自便.

最后

以上就是细心狗为你收集整理的数据结构之逆波兰表达式的全部内容，希望文章能够帮你解决数据结构之逆波兰表达式所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。