逆波兰表达式

目录

一、定义

二、算法步骤

三、代码实现

一、定义

      逆波兰表达式又叫做后缀表达式，是一种没有括号，并严格遵循“从左到右”运算的后缀式表达方法。

二、算法步骤

1、首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。

2、读入一个用中缀表示的简单算术表达式，为方便起见，设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。

3、从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。

4、如果不是数字，该字符则是运算符，此时需比较优先关系。

具体做法是：将该字符与运算符栈顶的运算符的优先关系相比较。如果该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。若不是的话，则将栈顶的运算符从栈中弹出，直到栈项运算符的优先级低于当前运算符，将该字符入栈。

5、重复步骤1～2，直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

三、代码实现

中缀转后缀

根据算术计算的优先级将要依次实现的步骤用括号括起来，然后将算术运算符移到最近的括号外。

然后把所有括号删除，根据从左到右的顺序放入栈中，遇到运算符就进行计算，先拿出目前的栈顶元素为num2，然后再拿出新的栈顶元素为num1，然后让num1(运算符)num2进行计算，将计算结果再放入栈内。

import java.util.Stack;


 private boolean isOperation(String s){ //判断是否为运算符

        if (s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){

            return true;

        }

        return false;

    }

public class Test {
    
    public int evalRPN(String[] tokens){

        Stack<Integer>stack=new Stack<>();


        for (String x:tokens){

            if (!isOperation(x)){

                stack.push(Integer.parseInt(x));

            }else {

                int num2=stack.pop();

                int num1=stack.pop();

                switch (x){

                    case "x":

                        stack.push(num1+num2);

                        break;

                    case "-":

                        stack.push(num1-num2);

                        break;

                    case "*":

                        stack.push(num1*num2);

                        break;

                    case "/":

                        stack.push(num1/num2);

                        break;

                }

            }


        }


        return stack.pop();

    }

   
}

最后栈内只有一个元素，这个元素就是这个运算表达式的结果。