[Java实现]逆波兰式

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[Java实现]逆波兰式，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3601字，纯文字阅读大概需要6分钟。

内容图文

前言：一个表达式有中缀表达式，前缀表达式，后缀表达式三种表示方法，

如1+2*3-8/2=3,因为操作符以中缀形式处于操作数的中间叫做中缀表达式
后缀表达式：运算符在操作数的后面。 上式的后缀表达式就是123*+82/-

虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。

中缀表达式转后缀

要将一个中缀表达式转化成后缀表达式，需要用到栈这个数据结构，它有一个重要的性质：后进先出，这是这个程序的基础。

步骤：

1. 初始化一个运算符栈，用于存储运算符。 初始化一个list，用于存放后缀表达式,然后从左到右扫描表达式

2. 遇到数字，直接存到list中

3. 当读到运算符时，分两种情况讨论

   1. 当运算符栈为空或者栈顶运算符的优先级小于当前运算符的优先级时，或者栈顶为左括号时，直接入栈。
   2. 运算符栈不为空且栈顶操作符的优先级大于当前运算符优先级时，循环执行运算符出栈并加入list中，直到遇到优先级小于等于当前运算符的元素为止，循环执行完后再将当前运算符压栈

4. 当遇到左括号时，直接压栈

5. 当遇到右括号时，循环执行出栈操作并加入到list中，直到遇到左括号为止，并将左括号弹出，但不加入到list中，丢弃这对括号

实现代码

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.Scanner;
import java.util.ArrayList;
/**
 * date :2020-12-2
 * author: wingchi-ye
 * 测试： 输入表达式正常时运行正常
 * 				没有校验表达式格式正确性
 */
class test{
    public static void main(String args[]) throws IOException {
        char str[];      
        Scanner Reader =new Scanner(System.in) ;
        Calculator cal =new Calculator();
        for(int i=0;i<2;i++){
            str =Reader.nextLine().toCharArray(); 
            ArrayList<Character> list = cal.toReverse_polish_type(str); /*转换成逆波兰式 */
            cal.calaExp(list) ; /**计算逆波兰式 */
        }
        Reader.nextLine();
    }
}

 class Calculator  {
    
    public  void calaExp(ArrayList<Character> exp){
        Iterator<Character> it=exp.iterator();
        Deque <Integer> stack =new ArrayDeque<Integer>();
        while(it.hasNext()) {
            char ch =it.next() ;
            if(ch-'0' <=9 &&ch-'0'>=0) stack.addFirst((int)ch-'0') ;
            else {
                stack.addFirst( calc (stack.removeFirst() , stack.removeFirst() ,ch )) ;
            }
        }
        int ans= stack.removeFirst(); 
        System.out.println(ans);
        
    }
    public int calc(int a1,int a2,char ch) {
        switch(ch){
            case 'x' : return a1*a2;
            case '/': return a2/a1;
            case '+': return a1+a2;
            case '-': return a2-a1 ;
            case '*': return a1*a2;
            default : return 0; 
        }
    }

    public ArrayList<Character> toReverse_polish_type (char[] str){
        Deque <Character> stack =new ArrayDeque<Character>();
        ArrayList<Character> expression =new ArrayList<>() ;
        Character ch  ;
        for(int i=0;i<str.length;i++) {
            ch = str[i] ;
            if(ch-'0' <= 9 && ch-'0' >=0 )
                expression.add(ch) ;
            else if(ch=='(' || ch==')'){
                if(ch=='(') stack.addFirst(ch) ;
                else {
                    /**右括号:依次弹出运算符栈的运算符并压入list,直到遇到左括号为止,然后将这对括号丢弃 */
                    char tmp = ' ';
                    while( (tmp=stack.removeFirst()) !='(') {
                        expression.add(tmp) ;
                    }
                }
            }
            else {
                if(stack.isEmpty() || isVaild(ch,stack.getFirst())) 
                    stack.addFirst(ch) ;
                else {
                    /**优先级小于等于的*/
                   while(stack.isEmpty()==false && !isVaild(ch,stack.peekFirst()) ){
                       expression.add(stack.removeFirst()); 
                   }
                   stack.addFirst(ch) ; /** */
                }
            }
        } 
        while(!stack.isEmpty()) expression.add(stack.removeFirst()) ;
        showlist(expression) ;
        return expression; 
    }
    /**
     * 比较两个运算符的优先级,并且判断栈顶元素是否为左括号 
     * @param s1
     * @param inStack:栈顶元素
     * @return s1优先级和s2高 : true
     *         相等或小于返回false
     */
    public boolean isVaild(char s1,char inStack){
        if(inStack=='(') return true ;
        if(s1=='x' || s1=='/' || s1=='*') {
            if(inStack=='+' || inStack=='-') return true ;
            return false ; 
        }
        return false; 

    }
    public void showlist(ArrayList<Character> list){
        for(int i=0;i<list.size() ;i++){
            System.out.print(list.get(i)) ;
        }
        System.out.println() ;
    }
  
}

内容总结

以上是互联网集市为您收集整理的[Java实现]逆波兰式全部内容，希望文章能够帮你解决[Java实现]逆波兰式所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端