java的逆波兰式算法

dq1618

浏览: 57672 次
性别:
来自: 成都

最近访客更多访客>>

dackylike

jiegao111

布衣凌宇

w4467147

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (19)

社区版块

存档分类

算法 Java 数据结构

Expression

java 代码

package expression;
import java.io.*;
import java.util.*;
public class Expression {
private ArrayList expression = new ArrayList();// 存储中序表达式
private ArrayList right = new ArrayList();// 存储右序表达式
private String result;// 结果
// 依据输入信息创建对象，将数值与操作符放入ArrayList中
private Expression(String input) {
StringTokenizer st = new StringTokenizer(input, "+-*/()", true);
while (st.hasMoreElements()) {
expression.add(st.nextToken());
}
}
// 将中序表达式转换为右序表达式
private void toRight() {
Stacks aStack = new Stacks();
String operator;
int position = 0;
while (true) {
if (Calculate.isOperator((String) expression.get(position))) {
if (aStack.top == -1
|| ((String) expression.get(position)).equals("(")) {
aStack.push(expression.get(position));
} else {
if (((String) expression.get(position)).equals(")")) {
if (!((String) aStack.top()).equals("(")) {
operator = (String) aStack.pop();
right.add(operator);
}
} else {
if (Calculate.priority((String) expression
.get(position)) <= Calculate
.priority((String) aStack.top())
&& aStack.top != -1) {
operator = (String) aStack.pop();
if (!operator.equals("("))
right.add(operator);
}
aStack.push(expression.get(position));
}
}
} else
right.add(expression.get(position));
position++;
if (position >= expression.size())
break;
}
while (aStack.top != -1) {
operator = (String) aStack.pop();
right.add(operator);
}
}
// 对右序表达式进行求值
private void getResult() {
this.toRight();
Stacks aStack = new Stacks();
String op1, op2, is = null;
Iterator it = right.iterator();
while (it.hasNext()) {
is = (String) it.next();
if (Calculate.isOperator(is)) {
op1 = (String) aStack.pop();
op2 = (String) aStack.pop();
aStack.push(Calculate.twoResult(is, op1, op2));
} else
aStack.push(is);
}
result = (String) aStack.pop();
it = expression.iterator();
while (it.hasNext()) {
System.out.print((String) it.next());
}
System.out.println("=" + result);
}
public static void main(String avg[]) {
try {
System.out.println("Input a expression:");
BufferedReader is = new BufferedReader(new InputStreamReader(
System.in));
for (;;) {
String input = new String();
input = is.readLine().trim();
if (input.equals("q"))
break;
else {
Expression boya = new Expression(input);
boya.getResult();
}
System.out
.println("Input another expression or input 'q' to quit:");
}
is.close();
} catch (IOException e) {
System.out.println("Wrong input!!!");
}
}
}

java 代码

package expression;
public class Calculate {
// 判断是否为操作符号
public static boolean isOperator(String operator) {
if (operator.equals("+") || operator.equals("-")
|| operator.equals("*") || operator.equals("/")
|| operator.equals("(") || operator.equals(")"))
return true;
else
return false;
}
// 设置操作符号的优先级别
public static int priority(String operator) {
if (operator.equals("+") || operator.equals("-")
|| operator.equals("("))
return 1;
else if (operator.equals("*") || operator.equals("/"))
return 2;
else
return 0;
}
// 做2值之间的计算
public static String twoResult(String operator, String a, String b) {
try {
String op = operator;
String rs = new String();
double x = Double.parseDouble(b);
double y = Double.parseDouble(a);
double z = 0;
if (op.equals("+"))
z = x + y;
else if (op.equals("-"))
z = x - y;
else if (op.equals("*"))
z = x * y;
else if (op.equals("/"))
z = x / y;
else
z = 0;
return rs + z;
} catch (NumberFormatException e) {
System.out.println("input has something wrong!");
return "Error";
}
}
}

java 代码

package expression;
import java.util.*;
//栈类
public class Stacks{
private LinkedList list=new LinkedList();
int top=-1;
public void push(Object value){
top++;
list.addFirst(value);
}
public Object pop(){
Object temp=list.getFirst();
top--;
list.removeFirst();
return temp;
}
public Object top(){
return list.getFirst();
}
}

分享到：

SimpleFormController流程 | struts 常见错误

2007-05-28 16:45
浏览 9062
评论(8)
查看更多

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

不错，正好最近需要用到这个。

发表评论

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

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论