cjf068
- 浏览: 33429 次
- 性别:
- 来自: 北京
-
最新评论
-
cjf068：
LuckYes 写道楼主如果用最小堆的话，最好用调整堆的方式来 ...
求最小的k个数问题 -
LuckYes：
楼主如果用最小堆的话，最好用调整堆的方式来构建堆，这样效率更高 ...
求最小的k个数问题 -
cjf068：
这个算法的基本思路， ...
大数乘法 -
liujunsong：
这个算法的基本思路，是小学3年级的 算法，就是简单的把乘法运算 ...
大数乘法 -
shuidexiongdi：
去年我也写了一个http://shuidexiongdi.it ...
大数乘法
计算n个数的全排列
计算24点，简单表达式计算
package org.jf.alg.stack;
import java.util.List;
import java.util.ArrayList;
public class PermUtil {
/**
* @param args
*/
public static void main(String[] args)
{
List<String[]> list = perm(new String[]{"a","b","c","d"},0,4,null);
List<String> source = new ArrayList<String>();
String ss [] = list.get(0);
for(String s:ss)
{
source.add(s);
}
List<List<String>> container = new ArrayList<List<String>>();
System.out.println(container.size());
// for(String[] ss:list)
// {
// printArray(ss);
// }
System.out.println(list.size());
}
/**
*
* void perm (char *a, const int k，const int n) {
// n 是数组a的元素个数，生成a[k],…,a[n-1]的全排列
int i;
if (k = = n-1) { // 终止条件，输出排列
for ( i=0; i<n; i++) cout << a[i] << “ ”; // 输出包括前
// 缀，以构成整个问题的解
cout << endl;
}
else { // a[k],…,a[n-1] 的排列大于1，递归生成
for ( i = k; i < n; i++) {
char temp = a[k]; a[k] = a[i]; a[i] = temp; // 交换a[k]
// 和 a[i]
perm(a,k+1,n); // 生成 a[k+1],…,a[n-1]的全排列
temp = a[k]; a[k] = a[i]; a[i] = temp; // 再次交换 a[k] 和
// a[i] , 恢复原顺序
}
} // else结束
} // perm结束
* 求全排列
* @param s
* @param start
* @param end
* @return
*/
public static List<String[]> perm(String []s,int k,int n,List<String[]> result)
{
List<String[]> result1= result;
if (k == n-1)
{
String ss [] = new String[s.length];
for( int i = 0;i<=n-1; i++)
{
ss[i] = s[i];
}
if(result1==null)
result1 = new ArrayList<String[]>();
result1.add(ss);
}else
{
for(int i = k;i<n;i++)
{
String tmp = s[k];
s[k] = s[i];
s[i] = tmp;
result1 = perm(s,k+1,n,result1);
tmp = s[k];
s[k] = s[i];
s[i] = tmp;
}
}
return result1;
}
static void printArray(String[] a)
{
for(String s:a)
{
System.out.print(s+" ");
}
System.out.println();
}
}
计算24点，简单表达式计算
package org.jf.alg.stack;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
public class OperationUtil
{
/**
* 中缀表达式转为后缀表达式
* (1)获取下一个输入标记
* (2)如果标记是:
* 左括号:将其压入表达式栈
* 右括号:连续弹出并显示栈中的元素，直到遇到一个左括号
* 一个运算符:如果栈为空，或者标记具有比栈顶元素更高的优先级，则将其压入栈中，否则弹出并显示
* 栈顶元素；接着继续比较标记和新的栈顶元素
* 一个操作数:显示它
* (3)当到到中缀表达式结尾时，弹出并显示栈中的元素直到栈空
* @param middleFixString
* @param fraction
* @return
*/
public static List<String> toPostfixExp(String middleFixString,boolean fraction)
{
Stack<String> opSt = new Stack<String>();
List<String> postExpList = new ArrayList<String>();
List<String> eleList = getElementList(middleFixString,fraction);
for(String ele:eleList)
{
char c = ele.charAt(0);
if(ele.length()==1 && !(c>='0' && c<='9'))
{
switch(c)
{
case '(' :
opSt.push(ele);
break ;
case ')' :
for(;;)
{
if(opSt.isEmpty())
break;
String op = opSt.pop();
if(op .equals("("))
break;
postExpList.add(op);
}
break ;
default:
if(opSt.isEmpty())
opSt.push(ele);
else
{//比较优先级
while(!opSt.isEmpty())
{
char opTop = opSt.peek().charAt(0);
if(opSt.isEmpty()||opTop == '(')
{
opSt.push(ele);
break;
}
if(getPriority(c)>getPriority(opTop))
{
opSt.push(ele);
break;
}
else
{
postExpList.add(opSt.pop());
opSt.push(ele);
break;
}
}
}
}
}
else
{
postExpList.add(ele);
}
}
while(!opSt.isEmpty())
{
postExpList.add(opSt.pop());
}
return postExpList;
}
private static List<String> getElementList(String middleFixExp,boolean fraction)
{
List<String> list = new ArrayList<String>();
char [] seprator = null;
if(fraction)
seprator = new char[]{'+','-','*','(',')'};
else
seprator = new char[]{'+','-','/','*','(',')'};
int opBeginIndx = -1;
boolean isOperator = false;
for(int i=0;i<middleFixExp.length();i++)
{
char curChar = middleFixExp.charAt(i);
isOperator = false;
for(int j=0;j<seprator.length;j++)
{
if(seprator[j] == curChar)
{
if(opBeginIndx != -1)
list.add(middleFixExp.substring(opBeginIndx, i));
list.add(curChar+"");
isOperator = true;
opBeginIndx = -1;
break;
}
}
if(isOperator)
continue;
if(opBeginIndx == -1)
opBeginIndx = i;
}
if(opBeginIndx != -1)
list.add(middleFixExp.substring(opBeginIndx));
return list;
}
public static String evaluate(String exp,boolean fraction) throws Exception
{
Stack<String> sta = new Stack<String>();
List<String> list = toPostfixExp(exp,fraction);
String s ="";
while(list.size()>0)
{
s = list.remove(0);
if(s.length()==1 && !(s.charAt(0)>='0'&&s.charAt(0)<='9'))
{
String y = sta.pop();
String x = sta.pop();
if("+-*/".indexOf(s)>=0)
{
String result = "";
if(fraction)
result =caculateFraction(x,y,s.charAt(0));
else
result =caculateInteger(x,y,s.charAt(0));
sta.push(result);
}
else throw new RuntimeException("not support operator:"+s);
}
else
{
sta.push(s);
}
}
return sta.pop();
}
public static String evaluate(List<String> postfix_exp,boolean fraction) throws Exception
{
Stack<String> sta = new Stack<String>();
String s ="";
while(postfix_exp.size()>0)
{
s = postfix_exp.remove(0);
if(s.length()==1 && !(s.charAt(0)>='0'&&s.charAt(0)<='9'))
{
String y = sta.pop();
String x = sta.pop();
if("+-*/".indexOf(s)>=0)
{
String result = "";
if(fraction)
result =caculateFraction(x,y,s.charAt(0));
else
result =caculateInteger(x,y,s.charAt(0));
sta.push(result);
}
else throw new RuntimeException("not support operator:"+s);
}
else
{
sta.push(s);
}
}
return sta.pop();
}
private static String caculateInteger(String x,String y,char operator)throws Exception
{
int px = Integer.parseInt(x);
int py = Integer.parseInt(y);
int result = 0;
switch(operator)
{
case '+':
result = px + py;
break;
case '-' :
result = px - py ;
break;
case '*' :
result = px * py;
break;
case '/' :
result = px / py;
break;
}
return result+"";
}
private static String caculateFraction(String x,String y,char operator)
{
int dx = 1, dy = 1,nx = 1, ny = 1;
if(x.indexOf("/")>0)
{
dx = Integer.parseInt(x.substring(x.indexOf("/")+1));
nx = Integer.parseInt(x.substring(0,x.indexOf("/")));
}else
{
nx = Integer.parseInt(x);
}
if(y.indexOf("/")>0)
{
dy = Integer.parseInt(y.substring(y.indexOf("/")+1));
ny = Integer.parseInt(y.substring(0,y.indexOf("/")));
}else
{
ny = Integer.parseInt(y);
}
String s = "";
int sn = 0;
int sd = 1;
switch(operator)
{
case '+':
sn = nx*dy+ny*dx;
sd = dx*dy;
break;
case '-':
sn = nx*dy-ny*dx;
sd = dx*dy;
if(sn%sd==0)
s = (sn/sd)+"";
else
s = sn+"/"+sd;
break;
case '*':
sn = nx*ny;
sd = dx*dy;
break;
case '/':
sn = nx*dy;
sd = ny*dx;
break;
}
if(sn%sd==0)
s = (sn/sd)+"";
else
s = sn+"/"+sd;
return s;
}
private static int getPriority(char operator)
{
switch(operator)
{
case '+':
return 0;
case '-':
return 0;
case '*' :
return 1;
case '/' :
return 1;
case '%' :
return 1;
default :
return -1;
}
}
/**
*
* @param source 操作数集合
* @return
*/
public static List<List<String>> getAllPostfixExp(List<String> source)
{
List<List<String>> container = new ArrayList<List<String>>();
Stack<String> st = new Stack<String>();
st.push(source.get(0));
fn2(source,1,true,source.size()-1,st,container);
// fn(source,1,st,container);
return container;
}
/**
*
* @param source
* @param k
* @param st
* @param container
*/
private static void fn(List<String> source,int k,Stack<String> st,List<List<String>> container)
{
if(container == null)
throw new RuntimeException("container is null");
String []operators = new String[]{"+","-","/","*"};
if(k>=source.size())
return;
st.push(source.get(k));
for(String op:operators)
{
st.push(op);
if(k==source.size()-1)
{
List<String> sta = new ArrayList<String>();
sta.addAll(st);
container.add(sta);
}else
{
fn(source,k+1,st,container);
}
st.pop();
}
st.pop();
}
/**
*
* @param source
* @param k 当前插入序号
* @param st
* @param rest_operator_num 还剩几个操作符没有插入
* @param container
*/
private static void fn2(List<String> source,int k,boolean push,
int rest_operator_num,Stack<String> st,List<List<String>> container)
{
if(container == null)
throw new RuntimeException("container is null");
String []operators = new String[]{"+","-","/","*"};
if(k>=source.size())
return;
if(push)
st.push(source.get(k));
//本次最多能插入的操作符个数
int max_num = rest_operator_num-(source.size()-1-k);
if(k == source.size()-1)//将剩余的所有操作符推入
{
for(int j=0;j<max_num;j++)
{
for(String op:operators)
{
st.push(op);
if(j == max_num-1)
{
List<String> sta = new ArrayList<String>();
if(st.size()==source.size()*2-1)//有一bug 计算出来的表达式比实际的多 尚未找到bug出在哪里 尚且在此判断 去除不合法的表达式
{
sta.addAll(st);
container.add(sta);
}
}else
{
fn2(source,k,false,max_num-j-1,st,container);//?
}
st.pop();
}
}
}else
{
for(int i=0;i<=max_num;i++)
{
if(i!=0)//push i 个操作符
pushOperator(i,source,k,false,rest_operator_num-i,st,container);
else if(i ==0)
{
fn2(source,k+1,true,rest_operator_num,st,container);
}
}
}
if(push)
st.pop();
}
private static void pushOperator(int num,
List<String> source,int k,boolean push,
int rest_operator_num,Stack<String> st,List<List<String>> container)
{
String []operators = new String[]{"+","-","/","*"};
if(num<1)
return;
for(String op:operators)
{
st.push(op);
if(num == 1)
{
fn2(source,k+1,true,rest_operator_num,st,container);
}
else
{
pushOperator(num-1,source,k,push,rest_operator_num,st,container);
}
st.pop();
}
}
public static void main(String args[])
{
// System.out.println(Integer.parseInt("4/5"));
List<String> source = new ArrayList<String>();
source.add("2");
source.add("2");
source.add("4");
source.add("8");
// List<List<String>> container = getAllPostfixExp(source);
// System.out.println(container.size());
// String s ="+";
// System.out.println(s.length()==0 && !(s.charAt(0)>='0'&&s.charAt(0)<='9'));
// List<String> list = toPostfixExp("12+((3*(2-4/5))+5)*3",true);
// System.out.println(OperationUtil.evaluate("3+2-9/4", true));
// List<List<String>> all = getAllPostfixExp(source);
// for(int i=0;i<all.size();i++)
// {
//
// for(String s:all.get(i))
// {
// System.out.print(s+" ");
// }
// System.out.println();
// }
// System.out.println(all.size());
long begin = System.currentTimeMillis();
// find24(new String[]{"4","5","5","1","6"});
find24(new String[]{"8","3","8","3"});
long end = System.currentTimeMillis();
System.out.println(end-begin);
// test8383();
}
public static void find24(String [] ops)
{
List<String[]> list = PermUtil.perm(ops, 0, ops.length, null);
for(String ss[]:list)
{
List<String> list1 = new ArrayList<String>();
for(String s:ss)
{
list1.add(s);
}
List<List<String>> expList = getAllPostfixExp(list1);
// System.out.println("exp list size = "+expList.size());
for(List<String> exp:expList)
{
StringBuffer sbu = new StringBuffer();
for(String str:exp)
{
sbu.append(str).append(" ");
}
// System.out.println(sbu.toString());
String result = "";
try {
result = evaluate(exp,true);
} catch (Exception e) {
// TODO Auto-generated catch block
// e.printStackTrace();
continue;
}
if("24".equals(result))
{
System.out.println("find success:"+sbu.toString());
// System.out.println();
}
}
}
}
static void test8383()
{
List<String> source = new ArrayList<String>();
source.add("8");
source.add("3");
source.add("8");
source.add("3");
List<List<String>> all = getAllPostfixExp(source);
for(int i=0;i<all.size();i++)
{
for(String s:all.get(i))
{
System.out.print(s+" ");
}
System.out.println();
}
System.out.println(all.size());
}
}
分享到：
发表评论
-
中文数字到阿拉伯数字转换
2012-04-24 10:18 1847昨天博客上看到一童鞋 ... -
布隆过滤器
2012-04-23 15:39 925package org.jf.alg; import ... -
基本的排序算法
2012-04-21 21:07 711插入排序 选择排序 快速排序 。。。。 后续补充 pack ... -
日期计算
2012-04-19 23:04 831简单日期计算类： 日期大小比较 日期之间天数计算 pack ... -
判断数组中是否存在两个元素之和等于给定数值
2012-04-06 22:58 1949已知int数组a按升序排列，要求用线性时间复杂的算法，判断是否 ... -
求最大子数组之和
2012-04-06 22:51 1274求最大子数组之和的线性解法：本算法受编程珠玑中提示而得 /** ... -
LRUCache
2012-03-15 14:35 1575MyLRUCache 缓存类 package org.jf ... -
求变位词组合
2012-03-13 22:53 823public class CharComp { ... -
表达式计算
2012-03-10 23:02 875中缀表达式转后缀 后缀表达式计算 支持整型 分数计算，只支持 ... -
Many2One缓冲
2012-03-06 12:35 902多线程并发操作中，为了尽量减少同步锁的开销，一般都会尽可能减少 ... -
红黑树
2012-03-03 21:47 1177红黑树 规则 * 1.每个 ... -
行文件分组统计
2012-03-02 22:57 804有些情况下，对于一个结构化的以行为记录的文本文件，需要按列分组 ... -
简单LRU缓存实现
2012-02-09 21:12 1052链表保存键值，由于没有权值策略，简单的将当前访问过的节点放到链 ... -
大根堆
2012-02-08 22:23 1389大根堆，可用于优先级队列 package org.jf.a ... -
固定容量二叉堆
2012-02-08 17:26 969固定容量的二叉堆实现，可用于快速求top k 问题。如要求一个 ... -
大数乘法
2012-02-07 00:16 2818论坛看到的一个面试题，实现任意大整数字符串相乘，返回结果字符串 ...
相关推荐
简易计算24点源代码 可输出多种不同结果 适合C语言初学者
用来计算24点的程序
这是第一个24点，大家可以参考，改进； 大家互相学习，谢谢 作者QQ2051510483
能计算24点，可以加括号，更换运算顺序，更换运算组合，能够算出所有24点组合
四张扑克牌计算二十四点的程序。 有了它，什么8833,7744,10 10 4 4都不怕了。 如果运行不了，请先安装VC2005发布程序，为了安全，可到微软的网站下载。
此游戏是基于本人在本科时所写...其将日常生活中的“计算24点游戏”以游戏程序的方式来呈现给各位朋友，属于一个智力游戏。虽然，其尚且存在一些不足之处，但还是足以激发大家对计算类的智力游戏的兴趣，希望各位喜欢！
算24点的一个小游戏的完整代码，通过24点的算法，把所有可能都列举出来，并且用户可以随机抽取四张牌进行口算。
在Java中实现类似JavaScript中eval()函数相似的功能，同时使用实现的evel实现4个数计算24点的应用。
数据结构课程设计(计算24点） 有2、3、4、5、6、7、8、9、10、J、Q、K、A张牌，编一程序，判断对任意给定的4张牌，能否在进行加、减、乘、除运算后，其运算结果等于24。其中J按11计算，Q按12计算，K按13计算，A按1...
其将日常生活中的“计算24点游戏”以游戏程序的方式来呈现给各位朋友，属于一个智力游戏。虽然，其尚且存在一些不足之处，但还是足以激发大家对计算类的智力游戏的兴趣，希望各位喜欢！这个资源是此游戏的源代码，以...
给定任意四个整数，自动给出一个计算公式，可计算出结果为24。
计算24点的各种方法 输入1~13的4个数，可以计算24点的各种方法
输入任意四个整数(0到10)，运算符只有加减乘除，还有括号.每个数只能且必须用一次。要求判断这些表达的结果中是否有24。如果有，输出计算表达式：如输入4，6，1，1 输出 4*6*1*1 =24 （允许有括号）。
计算24点
使用c++编写的24点程序，排除了大部分的重复情况。 使用的visoul C++提供的MFC编写
本程序是一个计算24点的小程序。当作是学习和娱乐吧。
计算24点的python程序。例： Input: $ python z24.py 1 5 5 5 Output: 5*(5-(1/5)) end.
计算24点的C++源代码，里面用2种方式进行了10以内数字任取4个数算24点。 第一种是用递归的方式； 第二种方式采用后缀表达式。 更详细的思路说明及细节介绍请参考我的文章： ...
计算24点扑克，C#，代码+程序 计算24点扑克，C#，代码+程序
计算24点 只要有答案就能计算出 包括复杂的小数计算 逻辑：1）4位数 + （ ）的所有组合 2）计算每个组合的值 值为24出结果 测试：执行test24 输入4个数字运行即可 src:[5 5 5 1] result:5 5 1 5 24 0 src:[7 8 9 ...