import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
*
* 应用：逆波兰表达式
*
* @author Leon.Chen
*
*/
public class CalculateString {
public BigDecimal calculateString(String str) {
char[] strs = str.toCharArray();
Stack<String> stack = new Stack<String>();
for (int i = 0; i < strs.length; i++) {
String stackStr = String.valueOf(strs[i]);
stack.push(stackStr);
if (")".equals(stack.top())) {
String subStr = null;
while (!"(".equals(stack.top())) {
stack.pop();
if (!"(".equals(stack.top())) {
subStr = addEnd(subStr, stack.top());
}
}
String pushStr = CalculateReversePolishExpression(subStr);
stack.pop();
stack.push(pushStr);
}
}
String resultStr = null;
while (stack.count != 0) {
resultStr = CalculateReversePolishExpression(stack.toString());
}
BigDecimal result = null;
if (resultStr != null) {
result = new BigDecimal(resultStr);
} else {
result = BigDecimal.ZERO;
}
return result.setScale(2, BigDecimal.ROUND_HALF_UP);
}
public String[] matcher(String regex, String str) {
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(str);
List<String> list = new ArrayList<String>();
while (matcher.find()) {
list.add(matcher.group());
}
String[] result = new String[list.size()];
return list.toArray(result);
}
public List<String> createReversePolishExpression(String subStr) {
String regex = "\\d+\\.{0,1}\\d*";
String[] numbers = matcher(regex, subStr);
String changeStr = subStr.replaceAll(regex, "0").replaceAll("\\-\\-0",
"-1").replaceAll("\\+\\-0", "+1").replaceAll("\\*\\-0", "*1")
.replaceAll("\\/\\-0", "/1");
char[] chars = changeStr.toCharArray();
int index = 0;
List<String> list = new ArrayList<String>();
for (int i = 0; i < chars.length; i++) {
String str = String.valueOf(chars[i]);
if ("0".equals(str)) {
list.add(numbers[index++]);
} else if ("1".equals(str)) {
list.add("-" + numbers[index++]);
} else {
list.add(str);
}
}
List<String> suffix = new ArrayList<String>();
Stack<String> operator = new Stack<String>();
for (int i = 0; i < list.size(); i++) {
if (!isOperatorType(list.get(i))) {
suffix.add(list.get(i));
} else {
if (operator.count == 0) {
operator.push(list.get(i));
} else {
while (operator.count != 0&&compare(operator.top(), list.get(i)) >= 0) {
String top = operator.top();
operator.pop();
suffix.add(top);
}
operator.push(list.get(i));
}
}
}
while (operator.count != 0) {
suffix.add(operator.top());
operator.pop();
}
return suffix;
}
public String CalculateReversePolishExpression(String subStr) {
List<String> suffix = createReversePolishExpression(subStr);
Stack<Double> stack = new Stack<Double>();
for (int i = 0; i < suffix.size(); i++) {
if (!isOperatorType(suffix.get(i))) {
stack.push(Double.valueOf(suffix.get(i)));
} else {
Double current = stack.top();
stack.pop();
Double previous = null;
if (stack.count != 0) {
previous = stack.top();
stack.pop();
} else {
previous = new Double(0);
}
Double result = calculate(suffix.get(i), previous, current);
stack.push(result);
}
}
return stack.top().toString();
}
public String addEnd(String str, String a) {
StringBuffer buf = new StringBuffer();
buf.append(a);
if (str != null) {
buf.append(str);
}
return buf.toString();
}
public boolean isOperatorType(String str) {
if (str.equals("+") || str.equals("-") || str.equals("*")
|| str.equals("/")) {
return true;
}
return false;
}
public int compare(String op1, String op2) {
Integer iop1 = getOperator(op1);
Integer iop2 = getOperator(op2);
return iop1.compareTo(iop2);
}
public Integer getOperator(String op) {
if ("+".equals(op) || "-".equals(op)) {
return new Integer(0);
}
if ("*".equals(op) || "/".equals(op)) {
return new Integer(1);
}
return null;
}
public Double calculate(String op, Double previous, Double current) {
if ("+".equals(op)) {
return previous + current;
}
if ("-".equals(op)) {
return previous - current;
}
if ("*".equals(op)) {
return previous * current;
}
if ("/".equals(op)) {
return previous / current;
}
return null;
}
public static void main(String[] args) {
String[] strs = new String[]{"(5+6)*7","(-1)/(-3)","1/(-3)","-1/7","7+(3*5)-(8+20/2)","4-(4-3*5+(2*4)+100)/10"};
for(int i=0;i<strs.length;i++){
BigDecimal result = new CalculateString().calculateString(strs[i]);
System.out.println(result.toString());
}
}
}
package graph;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
*
* 应用：逆波兰表达式
*
* @author Leon.Chen
*
*/
public class CalculateString {
public BigDecimal calculateString(String str) {
char[] strs = str.toCharArray();
Stack<String> stack = new Stack<String>();
for (int i = 0; i < strs.length; i++) {
String stackStr = String.valueOf(strs[i]);
stack.push(stackStr);
if (")".equals(stack.top())) {
String subStr = null;
while (!"(".equals(stack.top())) {
stack.pop();
if (!"(".equals(stack.top())) {
subStr = addEnd(subStr, stack.top());
}
}
String pushStr = CalculateReversePolishExpression(subStr);
stack.pop();
stack.push(pushStr);
}
}
String resultStr = null;
while (stack.count != 0) {
resultStr = CalculateReversePolishExpression(stack.toString());
}
BigDecimal result = null;
if (resultStr != null) {
result = new BigDecimal(resultStr);
} else {
result = BigDecimal.ZERO;
}
return result.setScale(2, BigDecimal.ROUND_HALF_UP);
}
public String[] matcher(String regex, String str) {
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(str);
List<String> list = new ArrayList<String>();
while (matcher.find()) {
list.add(matcher.group());
}
String[] result = new String[list.size()];
return list.toArray(result);
}
public List<String> createReversePolishExpression(String subStr) {
String regex = "\\d+\\.{0,1}\\d*";
String[] numbers = matcher(regex, subStr);
String changeStr = subStr.replaceAll(regex, "0").replaceAll("\\-\\-0",
"-1").replaceAll("\\+\\-0", "+1").replaceAll("\\*\\-0", "*1")
.replaceAll("\\/\\-0", "/1");
char[] chars = changeStr.toCharArray();
int index = 0;
List<String> list = new ArrayList<String>();
for (int i = 0; i < chars.length; i++) {
String str = String.valueOf(chars[i]);
if ("0".equals(str)) {
list.add(numbers[index++]);
} else if ("1".equals(str)) {
list.add("-" + numbers[index++]);
} else {
list.add(str);
}
}
List<String> suffix = new ArrayList<String>();
Stack<String> operator = new Stack<String>();
for (int i = 0; i < list.size(); i++) {
if (!isOperatorType(list.get(i))) {
suffix.add(list.get(i));
} else {
if (operator.count == 0) {
operator.push(list.get(i));
} else {
while (operator.count != 0&&compare(operator.top(), list.get(i)) >= 0) {
String top = operator.top();
operator.pop();
suffix.add(top);
}
operator.push(list.get(i));
}
}
}
while (operator.count != 0) {
suffix.add(operator.top());
operator.pop();
}
return suffix;
}
public String CalculateReversePolishExpression(String subStr) {
List<String> suffix = createReversePolishExpression(subStr);
Stack<Double> stack = new Stack<Double>();
for (int i = 0; i < suffix.size(); i++) {
if (!isOperatorType(suffix.get(i))) {
stack.push(Double.valueOf(suffix.get(i)));
} else {
Double current = stack.top();
stack.pop();
Double previous = null;
if (stack.count != 0) {
previous = stack.top();
stack.pop();
} else {
previous = new Double(0);
}
Double result = calculate(suffix.get(i), previous, current);
stack.push(result);
}
}
return stack.top().toString();
}
public String addEnd(String str, String a) {
StringBuffer buf = new StringBuffer();
buf.append(a);
if (str != null) {
buf.append(str);
}
return buf.toString();
}
public boolean isOperatorType(String str) {
if (str.equals("+") || str.equals("-") || str.equals("*")
|| str.equals("/")) {
return true;
}
return false;
}
public int compare(String op1, String op2) {
Integer iop1 = getOperator(op1);
Integer iop2 = getOperator(op2);
return iop1.compareTo(iop2);
}
public Integer getOperator(String op) {
if ("+".equals(op) || "-".equals(op)) {
return new Integer(0);
}
if ("*".equals(op) || "/".equals(op)) {
return new Integer(1);
}
return null;
}
public Double calculate(String op, Double previous, Double current) {
if ("+".equals(op)) {
return previous + current;
}
if ("-".equals(op)) {
return previous - current;
}
if ("*".equals(op)) {
return previous * current;
}
if ("/".equals(op)) {
return previous / current;
}
return null;
}
public static void main(String[] args) {
String[] strs = new String[]{"(5+6)*7","(-1)/(-3)","1/(-3)","-1/7","7+(3*5)-(8+20/2)","4-(4-3*5+(2*4)+100)/10"};
for(int i=0;i<strs.length;i++){
BigDecimal result = new CalculateString().calculateString(strs[i]);
System.out.println(result.toString());
}
}
}
自己写的stack
public class Stack<T> {
public StackNode<T> stackTop;
public int count;
public void push(T info) {
StackNode<T> node = new StackNode<T>();
node.info = info;
node.link = stackTop;
stackTop = node;
count++;
}
public void pop() {
if(stackTop == null) {
System.out.println("null stack");
} else {
stackTop = stackTop.link;
count--;
}
}
public boolean isEmpty() {
return count == 0;
}
public T top() {
if(stackTop == null) {
return null;
}
return stackTop.info;
}
public String toString(){
Stack<T> other = new Stack<T>();
while(count != 0){
T top = top();
pop();
other.push(top);
}
StringBuffer buf = new StringBuffer();
while(other.count !=0){
buf.append(other.top());
other.pop();
}
return buf.toString();
}
}
public class Stack<T> {
public StackNode<T> stackTop;
public int count;
public void push(T info) {
StackNode<T> node = new StackNode<T>();
node.info = info;
node.link = stackTop;
stackTop = node;
count++;
}
public void pop() {
if(stackTop == null) {
System.out.println("null stack");
} else {
stackTop = stackTop.link;
count--;
}
}
public boolean isEmpty() {
return count == 0;
}
public T top() {
if(stackTop == null) {
return null;
}
return stackTop.info;
}
public String toString(){
Stack<T> other = new Stack<T>();
while(count != 0){
T top = top();
pop();
other.push(top);
}
StringBuffer buf = new StringBuffer();
while(other.count !=0){
buf.append(other.top());
other.pop();
}
return buf.toString();
}
}
stack节点
public class StackNode<T> {
public StackNode<T> link;
public T info;
}
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Eval {
public int eval(String exp){
List<String> list = infixExpToPostExp(exp);//转化成后缀表达式
return doEval(list);//真正求值
}
//遇到操作符压栈，遇到表达式从后缀表达式中弹出两个数，计算出结果，压入堆栈
private int doEval(List<String> list) {
Stack<String> stack = new Stack<String>();
String element;
int n1,n2,result;
try{
for(int i = 0; i < list.size();i++){
element = list.get(i);
if(isOperator(element)){
n1 = Integer.parseInt(stack.pop());
n2 = Integer.parseInt(stack.pop());
result = doOperate(n1,n2,element);
stack.push(new Integer(result).toString());
}else{
stack.push(element);
}
}
return Integer.parseInt(stack.pop());
}catch(RuntimeException e){
throw new IllegalExpressionException(e.getMessage());
}
}
private int doOperate(int n1, int n2, String operator) {
if(operator.equals("+"))
return n1 + n2;
else if(operator.equals("-"))
return n1 - n2;
else if(operator.equals("*"))
return n1 * n2;
else
return n1 / n2;
}
private boolean isOperator(String str){
return str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/");
}
private List<String> infixExpToPostExp(String exp){//将中缀表达式转化成为后缀表达式
List<String> postExp = new ArrayList<String>();//存放转化的后缀表达式的链表
StringBuffer numBuffer = new StringBuffer();//用来保存一个数的
Stack<Character> opStack = new Stack<Character>();//操作符栈
char ch,preChar;
opStack.push('#');
try{
for(int i = 0; i < exp.length();){
ch = exp.charAt(i);
switch(ch){
case '+':
case '-':
case '*':
case '/':
preChar = opStack.peek();
// 如果栈里面的操作符优先级比当前的大，则把栈中优先级大的都添加到后缀表达式列表中
while(priority(preChar) >= priority(ch)){
postExp.add(""+preChar);
opStack.pop();
preChar = opStack.peek();
}
opStack.push(ch);
i++;
break;
case '(':
// 左括号直接压栈
opStack.push(ch);
i++;
break;
case ')':
// 右括号则直接把栈中左括号前面的弹出，并加入后缀表达式链表中
char c = opStack.pop();
while(c != '('){
postExp.add("" + c);
c = opStack.pop();
}
i++;
break;
// #号，代表表达式结束，可以直接把操作符栈中剩余的操作符全部弹出，并加入后缀表达式链表中
case '#':
char c1;
while(!opStack.isEmpty()){
c1 = opStack.pop();
if(c1 != '#')
postExp.add("" + c1);
}
i++;
break;
//过滤空白符
case ' ':
case '\t':
i++;
break;
// 数字则凑成一个整数，加入后缀表达式链表中
default:
if(Character.isDigit(ch)){
while(Character.isDigit(ch)){
numBuffer.append(ch);
ch = exp.charAt(++i);
}
postExp.add(numBuffer.toString());
numBuffer = new StringBuffer();
}else{
throw new IllegalExpressionException("illegal operator");
}
}
}
}catch(RuntimeException e){
throw new IllegalExpressionException(e.getMessage());
}
return postExp;
}
private int priority(char op){//定义优先级
switch(op){
case'+':
case'-':
return 1;
case'*':
case'/':
return 2;
case'(':
case'#':
return 0;
}
throw new IllegalExpressionException("Illegal operator");
}
public static void main(String[] args) {
Eval eval = new Eval();
int result = eval.eval("2+3+55*22+21*2+(3+2)*3+4*3+3*4#");
System.out.println(result);
}
}
分享到：
发表评论
-
Consistent Hashing
2010-02-09 17:12 799import java.util.Collection; ... -
防止JAVA程序重复启动的一个另类解决办法
2009-03-31 20:29 1930http://www.iteye.com/topic/3773 ... -
简单LRU算法实现缓存
2009-03-27 11:31 1558http://www.blogjava.net/killme2 ... -
MappedByteBuffer内存映射
2009-03-15 21:26 2145通过把一个套接字通道(SocketChannel)注册到一个选 ... -
如何知道方法的调用者
2009-03-11 20:35 801http://www.iteye.com/topic/1317 ... -
JAVA中操作数据库方式与设计模式的应用
2009-03-11 15:02 838http://www.iteye.com/topic/1981 ... -
java调用Oracle EXP备忘
2009-03-10 11:28 1548http://www.blogjava.net/BlueDav ... -
关于java中volatile字段的ordering
2009-03-08 22:00 756多个volatile操作之间是有序的，compiler和处理 ... -
Initialize-on-demand Holder Class
2009-03-02 15:01 905public class Singleton { ... -
Interceptor的实现
2009-03-01 21:26 801public interface Action { p ... -
Quartz CronTrigger最完整配置说明
2009-02-15 15:12 996CronTrigger配置格式: 格 ... -
ClassLoader介绍
2009-01-21 13:24 804JVM在运行时会产生三个ClassLoader，Bootstr ... -
消息的发送与回调
2009-01-06 22:03 811/** * 回调接口 * @author ... -
自己编写IOC
2009-01-05 21:59 1176<?xml version="1.0&qu ... -
一个简单的多线程、断点下载Java程序
2008-12-10 20:49 1895//这个是任务Bean public cl ... -
生产者-消费者
2008-12-02 14:05 818package debug; import java.u ...
相关推荐
以上就是使用C语言实现中缀表达式转后缀表达式的基本思路。实际编写代码时，还需要处理更多细节，例如错误检查、字符串处理、输入验证等。通过这个过程，我们可以更好地理解计算机如何解析和计算数学表达式，这对于...
本主题主要涉及两个关键知识点：中缀表达式转后缀表达式和逆波兰表达式求值。 1. **中缀表达式转后缀表达式**： - **算法思想**：使用两个栈，一个用于存储操作数，一个用于存储运算符。遍历中缀表达式的每个字符...
例如，中缀转后缀可以使用Dijkstra的shunting-yard算法，它基于操作符优先级和括号处理。而前缀和后缀之间的转换可以通过构建抽象语法树（AST）然后遍历它来实现。 在实际应用中，后缀表达式通常用于计算器实现，...
人们熟悉的四则运算表达式称为中缀表达式，例如(23+34*45/(5+6+7))。在程序设计语言中，可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式（又称逆波兰表示法），并最终变为计算机可以直接执行的指令，得到...
本篇将详细介绍从中缀表达式转换为后缀表达式的方法，并探讨如何使用C语言实现四则运算。 中缀表达式是我们日常生活中最常见的表达式形式，例如 \(2 + 3 * 4\)。在这个表达式中，运算符位于操作数之间。然而，这种...
中缀 转换成 后缀表达式的 计算 多位数
中缀转后缀的转换过程通常涉及两个主要步骤：表达式的语法分析和栈操作。在这个C++程序中，`ball6v4`可能是一个特定版本或实现的标识符。以下是实现这个转换过程的一些关键知识点： 1. **表达式语法分析**：首先，...
在IT领域，四则运算表达式的转换和计算是计算机科学中的基本问题，特别是在编译原理、数据结构和算法设计中。这里我们主要讨论如何将中缀表达式转换为后缀表达式（也称为逆波兰表示法）以及如何计算后缀表达式的结果...
将一个表达式转为后缀表达式，用堆栈计算 中缀转后缀的过程中遇到数字直接输出，遇到符号则判断优先级。
将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如，整个表达式两端的括号要省略，不影响原计算顺序的括号要...
将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如，整个表达式两端的括号要省略，不影响原计算结果的括号要...
支持浮点数的四则运算，包含两种计算方法，一种中缀表达式（两个栈），另一种中缀表达式转后缀表达式。输入表达式求值计算
标题 "四则运算求值（中缀转逆波兰式）" 涉及到的是计算机科学中的算法问题，主要集中在表达式求值和转换方法上。逆波兰表示法（Reverse Polish Notation，RPN），也被称为后缀表示法，是一种没有括号的数学表达式...
在本主题中，我们将深入探讨如何使用Java实现四则运算，包括中缀表达式到后缀表达式的转换以及利用栈数据结构进行计算。 首先，我们要理解四则运算的基本概念，它们包括加法（+）、减法（-）、乘法（*）和除法（/）...
将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如，整个表达式两端的括号要省略，不影响原计算顺序的括号要...
"二叉树求四则运算" 在数据结构中，二叉树是一种常用的数据结构，它可以用来解决各种问题，例如四则运算。在本实验中，我们使用C/C++语言实现了一个二叉树求四则运算的程序。 首先，我们定义了一个Node类，它用于...
### 栈的应用——中缀转后缀 #### 一、概念理解 在程序设计与数据结构的学习中，栈是一种常见的线性数据结构，遵循“后进先出”（Last In First Out, LIFO）的原则。栈的应用十分广泛，其中一个重要的应用就是实现...
在编程领域，四则运算求值算法是计算机科学的基础，特别是在解释器和编译器设计中扮演着重要角色。本文档将重点讨论如何在C++中实现一个四则运算表达式的求值算法。C++是一种强大的面向对象的编程语言，其灵活性和...