`
dq1618
  • 浏览: 57606 次
  • 性别: Icon_minigender_1
  • 来自: 成都
文章分类
社区版块
存档分类
最新评论

java的逆波兰式算法

阅读更多
Expression
java 代码
  1. package expression;   
  2.   
  3. import java.io.*;   
  4. import java.util.*;   
  5.   
  6. public class Expression {   
  7.     private ArrayList expression = new ArrayList();// 存储中序表达式   
  8.   
  9.     private ArrayList right = new ArrayList();// 存储右序表达式   
  10.   
  11.     private String result;// 结果   
  12.   
  13.     // 依据输入信息创建对象,将数值与操作符放入ArrayList中   
  14.     private Expression(String input) {   
  15.         StringTokenizer st = new StringTokenizer(input, "+-*/()"true);   
  16.         while (st.hasMoreElements()) {   
  17.             expression.add(st.nextToken());   
  18.         }   
  19.     }   
  20.   
  21.     // 将中序表达式转换为右序表达式   
  22.     private void toRight() {   
  23.         Stacks aStack = new Stacks();   
  24.         String operator;   
  25.         int position = 0;   
  26.         while (true) {   
  27.             if (Calculate.isOperator((String) expression.get(position))) {   
  28.                 if (aStack.top == -1  
  29.                         || ((String) expression.get(position)).equals("(")) {   
  30.                     aStack.push(expression.get(position));   
  31.                 } else {   
  32.                     if (((String) expression.get(position)).equals(")")) {   
  33.                         if (!((String) aStack.top()).equals("(")) {   
  34.                             operator = (String) aStack.pop();   
  35.                             right.add(operator);   
  36.                         }   
  37.                     } else {   
  38.                         if (Calculate.priority((String) expression   
  39.                                 .get(position)) <= Calculate   
  40.                                 .priority((String) aStack.top())   
  41.                                 && aStack.top != -1) {   
  42.                             operator = (String) aStack.pop();   
  43.                             if (!operator.equals("("))   
  44.                                 right.add(operator);   
  45.                         }   
  46.                         aStack.push(expression.get(position));   
  47.                     }   
  48.                 }   
  49.             } else  
  50.                 right.add(expression.get(position));   
  51.             position++;   
  52.             if (position >= expression.size())   
  53.                 break;   
  54.         }   
  55.         while (aStack.top != -1) {   
  56.             operator = (String) aStack.pop();   
  57.             right.add(operator);   
  58.         }   
  59.     }   
  60.   
  61.     // 对右序表达式进行求值   
  62.     private void getResult() {   
  63.         this.toRight();   
  64.         Stacks aStack = new Stacks();   
  65.         String op1, op2, is = null;   
  66.         Iterator it = right.iterator();   
  67.   
  68.         while (it.hasNext()) {   
  69.             is = (String) it.next();   
  70.             if (Calculate.isOperator(is)) {   
  71.                 op1 = (String) aStack.pop();   
  72.                 op2 = (String) aStack.pop();   
  73.                 aStack.push(Calculate.twoResult(is, op1, op2));   
  74.             } else  
  75.                 aStack.push(is);   
  76.         }   
  77.         result = (String) aStack.pop();   
  78.         it = expression.iterator();   
  79.         while (it.hasNext()) {   
  80.             System.out.print((String) it.next());   
  81.         }   
  82.         System.out.println("=" + result);   
  83.     }   
  84.   
  85.     public static void main(String avg[]) {   
  86.         try {   
  87.             System.out.println("Input a expression:");   
  88.             BufferedReader is = new BufferedReader(new InputStreamReader(   
  89.                     System.in));   
  90.             for (;;) {   
  91.                 String input = new String();   
  92.                 input = is.readLine().trim();   
  93.                 if (input.equals("q"))   
  94.                     break;   
  95.                 else {   
  96.                     Expression boya = new Expression(input);   
  97.                     boya.getResult();   
  98.                 }   
  99.                 System.out   
  100.                         .println("Input another expression or input 'q' to quit:");   
  101.             }   
  102.             is.close();   
  103.         } catch (IOException e) {   
  104.             System.out.println("Wrong input!!!");   
  105.         }   
  106.     }   
  107. }   

 

java 代码
  1. package expression;   
  2.   
  3. public class Calculate {   
  4.     // 判断是否为操作符号   
  5.     public static boolean isOperator(String operator) {   
  6.         if (operator.equals("+") || operator.equals("-")   
  7.                 || operator.equals("*") || operator.equals("/")   
  8.                 || operator.equals("(") || operator.equals(")"))   
  9.             return true;   
  10.         else  
  11.             return false;   
  12.     }   
  13.   
  14.     // 设置操作符号的优先级别   
  15.     public static int priority(String operator) {   
  16.         if (operator.equals("+") || operator.equals("-")   
  17.                 || operator.equals("("))   
  18.             return 1;   
  19.         else if (operator.equals("*") || operator.equals("/"))   
  20.             return 2;   
  21.         else  
  22.             return 0;   
  23.     }   
  24.   
  25.     // 做2值之间的计算   
  26.     public static String twoResult(String operator, String a, String b) {   
  27.         try {   
  28.             String op = operator;   
  29.             String rs = new String();   
  30.             double x = Double.parseDouble(b);   
  31.             double y = Double.parseDouble(a);   
  32.             double z = 0;   
  33.             if (op.equals("+"))   
  34.                 z = x + y;   
  35.             else if (op.equals("-"))   
  36.                 z = x - y;   
  37.             else if (op.equals("*"))   
  38.                 z = x * y;   
  39.             else if (op.equals("/"))   
  40.                 z = x / y;   
  41.             else  
  42.                 z = 0;   
  43.             return rs + z;   
  44.         } catch (NumberFormatException e) {   
  45.             System.out.println("input has something wrong!");   
  46.             return "Error";   
  47.         }   
  48.     }   
  49. }   
java 代码
  1. package expression;    
  2. import java.util.*;    
  3. //栈类    
  4. public class Stacks{    
  5.    private LinkedList list=new LinkedList();    
  6.    int top=-1;    
  7.    public void push(Object value){    
  8.       top++;    
  9.       list.addFirst(value);    
  10.    }    
  11.    public Object pop(){    
  12.       Object temp=list.getFirst();    
  13.       top--;    
  14.       list.removeFirst();    
  15.       return temp;    
  16.   
  17.    }    
  18.    public Object top(){    
  19.    return list.getFirst();    
  20.    }    
  21. }    
分享到:
评论
8 楼 smiky 2010-07-22  
gongtao 写道
转你波兰表达式时有问题,转的不对

看下我的吧,应该没问题http://smiky.iteye.com/admin/blogs/718598
7 楼 smiky 2010-07-22  
#   if (((String) expression.get(position)).equals(")")) {  
#                         if (!((String) aStack.top()).equals("(")) {  
#                             operator = (String) aStack.pop();  
#                             right.add(operator);  
#                         }  
#                     } else {  
这一段会有问题,此时只出栈了一次,当有多个操作符的时候就会出问题了
这个地方要循环啦
6 楼 gongtao 2010-07-22  
转你波兰表达式时有问题,转的不对
5 楼 ct455332 2010-03-25  
你好厉害。。我是从C++转学过来的。C++的数据结构书里有逆波兰的方法。但是描述的原没有你这里这么简单。谢啦。研究研究看看能不能添加些自己的东西
4 楼 aigo_h 2009-12-23  
3+(3+3/3)*3
这个还有问题
3 楼 aigo_h 2009-12-23  
3+(3+3/3)*3
试试这个
还有问题
2 楼 classicbride 2009-06-04  
3ks... 启发很大,不过发现你的实现有个小小bug...

比如表达式为:80-(5*(1+2))*3 就会出错,原因在于设置操作符号的优先级别有点问题

Calculate.priority(String operator)

改了下代码:
        // 设置操作符号的优先级别   
	public static int priority(String operator) {   
		if (operator.equals("+") || operator.equals("-")){
			return 1;
		}   
	    else if (operator.equals("*") || operator.equals("/")){
	    	return 2;
	    }   
	    else if (operator.equals("(") || operator.equals(")")){
	    	return 3;
	    }
	    else {
	    	return 0;   
	    } 
	} 

1 楼 jindw 2008-10-11  
不错,正好最近需要用到这个。

相关推荐

    java 逆波兰式(这个是java版的还附有实验报告)

    - **java逆波兰式.txt**:这份文件很可能是Java程序的源代码,用于实现逆波兰式表达式的解析和计算功能。通过阅读代码,我们可以学习到如何在Java中利用栈数据结构来处理逆波兰表达式。 - **C逆波兰式.txt**:虽然...

    java带逆波兰式的科学计算器

    大三学生用Java编写逆波兰式计算器是一个很好的学习项目,可以加深对数据结构、算法和面向对象编程的理解。然而,实现"-(A+B)"这样的功能确实有一定难度,因为它需要在逆波兰式中表达嵌套的括号。一种可能的解决...

    逆波兰式的生成-(代码+原理图)

    逆波兰式的生成算法可以通过以下流程图来表示: ① 在表达式字符串的末尾加一个代表结束的辅助符,例如“#”。 ② 从头开始扫描表达式,并判断当前的一个字符。 ③ 取当前的一个字符,如果当前字符是代表数字,则将...

    java编写的逆波兰式转换方法

    逆波兰算法的java版,能够将运算字符串转换为逆波兰式,并尽心简单的错误判断处理!

    逆波兰式(JAVA版)

    Java作为一种通用的编程语言,同样可以用来实现逆波兰式相关的算法和功能。 在逆波兰式中,计算过程通常分为两个主要步骤:解析和计算。解析阶段是将常规的中缀表达式转换为逆波兰式,而计算阶段则是根据逆波兰式...

    逆波兰式的生成

    4. **波兰式转换算法**:将中缀表达式转换为逆波兰式的主要算法有以下两种: - **Shunting Yard算法**(又称推栈算法):由Edsger Dijkstra提出,它使用一个栈来辅助转换过程。首先扫描输入的中缀表达式,遇到操作...

    编程求取合式公式的波兰式和逆波兰式

    在计算机科学领域,波兰式(也称为前缀表示法)和逆波兰式(也称为后缀表示法)是表达算术或逻辑公式的不同...通过理解和使用这个程序,用户不仅可以了解波兰式和逆波兰式,还能深入理解解析算法和栈数据结构的应用。

    逆波兰式可执行代码

    在Java编程中,我们可以编写程序来实现中缀表达式到逆波兰式的转换,并使用逆波兰式进行表达式的求值。这个"中缀转后缀java可运行代码"项目提供了这样的功能,包括文件输入输出和表达式计算。以下是这个项目中可能...

    逆波兰式计算

    在提供的源码工具中,可能包含了一个逆波兰式计算器的实现,可能使用了C++、Java、Python等编程语言。通过阅读和理解代码,可以深入学习到如何使用栈数据结构进行表达式计算,以及如何实现表达式的语法解析。此外,...

    java 计算器 源码 逆波兰式

    在这个Java课程大作业中,我们关注的是一个使用逆波兰式算法实现的计算器源码。 逆波兰式的基本原理是将传统的中缀表达式(如2 + 3 * 4)转化为后缀表达式(如2 3 4 * +),运算符放在操作数之后。这种表示法消除了...

    nibol.zip_逆波兰_逆波兰式

    而"一个逆波兰式的生成程序"可能是实际的程序文件,可能用C、Python、Java等编程语言编写,用于接受中缀表达式输入并输出对应的逆波兰式。 逆波兰式生成通常涉及以下步骤: 1. 读取中缀表达式。 2. 使用词法分析器...

    java逆波兰表达式【栈】完整版

    【数据结构与算法】逆波兰表达式完整版,使用java语言编写。逆波兰表达式又叫做后缀表达式,是一种没有括号,并严格遵循“从左到右”运算的后缀式表达方法

    布尔翻译逆波兰式,完整实验报告,写上班级姓名即可

    布尔翻译逆波兰式是一种在计算机科学中用于表示布尔表达式的计算方法...通过理解和实践布尔翻译逆波兰式,不仅可以加深对布尔代数的理解,还能锻炼编程和算法设计能力,这对于计算机科学的学习者来说是非常宝贵的经验。

    逆波兰式的生成(包括输入表达式是否合法的判定)

    ### 逆波兰式的生成及其合法性判断 ...通过上述分析,我们不仅了解了逆波兰式的生成算法,还学习了如何判断一个数学表达式是否符合逆波兰式的生成规则。这对于理解和实现计算机科学中的表达式计算有着重要的意义。

    counter_逆波兰式_对数运算_

    逆波兰式,也被称为后缀表达式,是一种数学表达式的表示方法,它在计算领域有着广泛的应用,特别是在计算器设计和编译原理中。在这种表示法中,操作符位于其操作数之后,使得表达式无需括号就能明确表示优先级。例如...

    Java写的泥波兰式.rar_reverse polish_逆波兰_逆波兰式

    通过学习和理解逆波兰表达式及其Java实现,开发者可以提升对数据结构和算法的理解,特别是在设计和优化计算逻辑时。同时,逆波兰表达式也常用于编译器设计、计算器程序等领域,具有广泛的应用价值。

    四则运算求值(中缀转逆波兰式)

    标题 "四则运算求值(中缀转逆波兰式)" 涉及到的是计算机科学中的算法问题,主要集中在表达式求值和转换方法上。逆波兰表示法(Reverse Polish Notation,RPN),也被称为后缀表示法,是一种没有括号的数学表达式...

    android 逆波兰式计算器

    总的来说,"android 逆波兰式计算器"项目涉及到了Android应用开发、用户界面设计、逆波兰算法的实现以及正则表达式处理等多方面的技术知识。通过学习和理解这个项目,开发者可以提升自己在Android编程和算法应用方面...

    Android 带滑动、抽屉效果的逆波兰式计算器

    在Android开发中,创建一个带有滑动抽屉效果和逆波兰式计算器的App是一项具有挑战性的任务,它结合了UI设计和算法实现。这个项目主要涉及以下几个关键知识点: 1. **Android UI组件**:抽屉(Drawer)效果是Android...

Global site tag (gtag.js) - Google Analytics