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

java的逆波兰式算法

算法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. }    
分享到：
| struts 常见错误
评论
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  
不错，正好最近需要用到这个。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics