代码拉取完成，页面将自动刷新
package szys;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
class Rational {
private long m_up;
private long m_down;
public Rational() {
}
public Rational(long up, long down) {
super();
// 约分
long g = gcd(up >= 0 ? up : -up, down > 0 ? down : -down);
this.m_up = up / g;
this.m_down = down / g;
}
public long getM_up() {
return m_up;
}
public long getM_down() {
return m_down;
}
private static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
public Rational add(Rational r) {
long up = m_up * r.m_down + m_down * r.m_up;
long down = m_down * r.m_down;
return new Rational(up, down);
}
public Rational subtract(Rational r) {
long up = m_up * r.m_down - m_down * r.m_up;
long down = m_down * r.m_down;
return new Rational(up, down);
}
public Rational multiply(Rational r) {
long up = m_up * r.m_up;
long down = m_down * r.m_down;
return new Rational(up, down);
}
//不会有除0错误，哇哈哈哈！！！
public Rational divide(Rational r) {
long up = m_up * r.m_down;
long down = m_down * r.m_up;
return new Rational(up, down);
}
private static long quickPow(long a, int n) {
long res = 1;
while (n > 0) {
if ((n & 1) == 1) {
res *= a;
}
a *= a;
n >>= 1;
}
return res;
}
public Rational pow(int n) {
return new Rational(quickPow(m_up, n), quickPow(m_down, n));
}
@Override
public String toString() {
if (m_down < 0) {
m_up = -m_up;
m_down = -m_down;
}
return m_up + (m_down == 1 ? "" : "/" + m_down);
}
}
class Node {
private String val;
private Node left, right;
public Node() {
val = null;
left = right = null;
}
public Node(String val, Node left, Node right) {
super();
this.val = val;
this.left = left;
this.right = right;
}
public String getVal() {
return val;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
}
//比较两个最小表示法字符串的大小
class MinPreFormatComparator implements Comparator<MinPreFormat> {
@Override
public int compare(MinPreFormat o1, MinPreFormat o2) {
ArrayList<String> list1 = o1.getVal();
ArrayList<String> list2 = o2.getVal();
int lim = Math.min(list1.size(), list2.size());
for (int i = 0; i < lim; i++) {
if (!list1.get(i).equals(list2.get(i))) {
return list1.get(i).compareTo(list2.get(i));
}
}
return list1.size() - list2.size();
}
}
class MinPreFormat {
private ArrayList<String> val;
public MinPreFormat() {
}
public MinPreFormat(ArrayList<String> val) {
this.val = val;
}
public ArrayList<String> getVal() {
return val;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((val == null) ? 0 : val.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
MinPreFormat other = (MinPreFormat) obj;
if (val == null) {
if (other.val != null)
return false;
} else if (!val.equals(other.val))
return false;
return true;
}
}
class ExpAndAns {
String exp;
Rational ans;
public String getExp() {
return exp;
}
public Rational getAns() {
return ans;
}
public ExpAndAns() {
}
public ExpAndAns(String exp, Rational ans) {
super();
this.exp = exp;
this.ans = ans;
}
}
public class Arithmetic {
private static int count(char c) {
if (c == '=')
return 0;
if (c == '(')
return 1;
if (c == '+')
return 2;
if (c == '-')
return 3;
if (c == '*')
return 4;
if (c == '/')
return 5;
if (c == '^')
return 6;
return 7;
}
private static boolean isNum(String exp, int pos) {
char ch = exp.charAt(pos);
if (ch >= '0' && ch <= '9') {
return true;
}
return false;
}
private static String trans(String exp) {
// 负数都用括号括起来
for (int i = 0; i < exp.length(); i++) {
if (exp.charAt(i) == '-' && exp.charAt(i - 1) == '(') {
exp = exp.substring(0, i) + '0' + exp.substring(i, exp.length());
i++;
}
}
// System.out.println(exp);
String postexp = new String();
int lpri[] = { 0, 1, 3, 3, 5, 5, 7, 8 }; // =(+-*/^)
int rpri[] = { 0, 8, 2, 2, 4, 4, 6, 1 };
ArrayList<Character> op = new ArrayList<>();
op.add('=');
for (int i = 0; i < exp.length();) {
if (isNum(exp, i)) {
while (i < exp.length() && isNum(exp, i)) {
postexp += exp.charAt(i);
i++;
}
postexp += '#';
} else {
if (lpri[count(op.get(op.size() - 1))] < rpri[count(exp.charAt(i))]) {
op.add(exp.charAt(i));
i++;
} else if (lpri[count(op.get(op.size() - 1))] == rpri[count(exp.charAt(i))]) {
op.remove(op.size() - 1);
i++;
} else {
postexp += op.get(op.size() - 1);
op.remove(op.size() - 1);
}
}
}
while (!op.isEmpty() && op.get(op.size() - 1) != '=') {
postexp += op.get(op.size() - 1);
op.remove(op.size() - 1);
}
return postexp;
}
// 操作数不超过5个，操作符不超过4个，括号不超过3对，乘方只能有一个，而且次数只能小于等于3
private static final int MAX_NUMS = 5;
private static final int MIN_NUMS = 2;
private static final int MAX_PAIRS = 2;
private static String generateNewExp() {
// 产生基本的算式
String exp = new String();
Random random = new Random();
int nums = random.nextInt(MAX_NUMS - MIN_NUMS + 1) + MIN_NUMS;
int pairs = random.nextInt(MAX_PAIRS + 1);
HashMap<Integer, Integer> leftPosMap = new HashMap<>();
HashMap<Integer, Integer> rightPosMap = new HashMap<>();
for (int i = 0; i < nums; i++) {
leftPosMap.put(i + 1, 0);
rightPosMap.put(i + 1, 0);
}
for (int i = 0; i < pairs; i++) {
int leftPos = random.nextInt(nums) + 1;
int rightPos = random.nextInt(nums - leftPos + 1) + leftPos;
// System.out.println(leftPos + " " + rightPos);
leftPosMap.put(leftPos, leftPosMap.get(leftPos) + 1);
rightPosMap.put(rightPos, rightPosMap.get(rightPos) + 1);
}
boolean hasPow = false;
for (int i = 0; i < nums; i++) {
boolean needContinue = false;
if (i != 0) {
int op = random.nextInt(5);
switch (op) {
case 0:
exp += "+";
break;
case 1:
exp += "-";
break;
case 2:
exp += "*";
break;
case 3:
exp += "/";
break;
default:
if (hasPow) {
needContinue = true;
i--;
} else {
exp += "^";
hasPow = true;
}
break;
}
if (needContinue) {
continue;
}
}
int leftNums = leftPosMap.get(i + 1);
for (int j = 0; j < leftNums; j++) {
exp += "(";
}
if (exp.length() > leftNums && exp.charAt(exp.length() - leftNums - 1) == '^') {
int matchPos = i + 1;
for (int j = 0; j < leftNums; j++) {
exp = exp.substring(0, exp.length() - 1);
while (rightPosMap.get(matchPos) <= 0) {
matchPos++;
}
rightPosMap.put(matchPos, rightPosMap.get(matchPos) - 1);
}
exp += random.nextInt(4);
} else {
int generateNum = (random.nextInt(40) - 20);
if (generateNum < 0 && (leftPosMap.get(i + 1) == 0 || rightPosMap.get(i + 1) == 0)) {
exp += "(" + generateNum;
rightPosMap.put(i + 1, rightPosMap.get(i + 1) + 1);
} else {
exp += generateNum;
}
}
int rightNums = rightPosMap.get(i + 1);
for (int j = 0; j < rightNums; j++) {
exp += ")";
}
// System.out.println(exp);
}
return exp;
// 加括号
}
private static Rational calc(String postexp) {
ArrayList<Rational> st = new ArrayList<>();
// System.out.println(postexp);
for (int i = 0; i < postexp.length();) {
switch (postexp.charAt(i)) {
case '+':
Rational r1 = st.get(st.size() - 1);
st.remove(st.size() - 1);
Rational r2 = st.get(st.size() - 1);
st.remove(st.size() - 1);
st.add(r1.add(r2));
break;
case '-':
r1 = st.get(st.size() - 1);
st.remove(st.size() - 1);
r2 = st.get(st.size() - 1);
st.remove(st.size() - 1);
st.add(r2.subtract(r1));
break;
case '*':
r1 = st.get(st.size() - 1);
st.remove(st.size() - 1);
r2 = st.get(st.size() - 1);
st.remove(st.size() - 1);
st.add(r1.multiply(r2));
break;
case '/':
r1 = st.get(st.size() - 1);
st.remove(st.size() - 1);
r2 = st.get(st.size() - 1);
st.remove(st.size() - 1);
st.add(r2.divide(r1));
break;
case '^':
r1 = st.get(st.size() - 1);
st.remove(st.size() - 1);
r2 = st.get(st.size() - 1);
st.remove(st.size() - 1);
st.add(r2.pow((int) r1.getM_up()));
break;
default:
long num = 0;
while (i < postexp.length() && isNum(postexp, i)) {
num = num * 10 + postexp.charAt(i) - '0';
i++;
}
st.add(new Rational(num, 1));
break;
}
i++;
// for (Rational rational : st) {
// System.out.print(rational);
// System.out.print(" ");
// }
// System.out.println();
}
return st.get(st.size() - 1);
}
//产生除0的需要被T出
public static ArrayList<ExpAndAns> generateExps(int num) {
HashSet<MinPreFormat> hashSet = new HashSet<>();
ArrayList<ExpAndAns> res = new ArrayList<>();
for (int i = 0; i < num; i++) {
String exp = generateNewExp();
String postexp = trans(exp);
Node root = createExpTree(postexp);
MinPreFormat minPreFormat = minPre(root);
if (hashSet.contains(minPreFormat)) {
i--;
} else {
Rational ans = calc(postexp);
if (ans.getM_down() == 0) {
i--;
} else {
hashSet.add(minPreFormat);
res.add(new ExpAndAns(exp, ans));
}
}
}
return res;
}
private static Node createExpTree(String postexp) {
ArrayList<Node> st = new ArrayList<>();
for (int i = 0; i < postexp.length();) {
switch (postexp.charAt(i)) {
case '+':
Node nd1 = st.get(st.size() - 1);
st.remove(st.size() - 1);
Node nd2 = st.get(st.size() - 1);
st.remove(st.size() - 1);
st.add(new Node("+", nd2, nd1));
break;
case '-':
nd1 = st.get(st.size() - 1);
st.remove(st.size() - 1);
nd2 = st.get(st.size() - 1);
st.remove(st.size() - 1);
st.add(new Node("-", nd2, nd1));
break;
case '*':
nd1 = st.get(st.size() - 1);
st.remove(st.size() - 1);
nd2 = st.get(st.size() - 1);
st.remove(st.size() - 1);
st.add(new Node("*", nd2, nd1));
break;
case '/':
nd1 = st.get(st.size() - 1);
st.remove(st.size() - 1);
nd2 = st.get(st.size() - 1);
st.remove(st.size() - 1);
st.add(new Node("/", nd2, nd1));
break;
case '^':
nd1 = st.get(st.size() - 1);
st.remove(st.size() - 1);
nd2 = st.get(st.size() - 1);
st.remove(st.size() - 1);
st.add(new Node("^", nd2, nd1));
break;
default:
String num = new String();
while (i < postexp.length() && isNum(postexp, i)) {
num += postexp.charAt(i);
i++;
}
st.add(new Node(num, null, null));
break;
}
i++;
}
return st.get(st.size() - 1);
}
private static MinPreFormat minPre(Node root) {
if (root == null) {
return null;
}
MinPreFormat LeftMinPre = minPre(root.getLeft());
MinPreFormat RightMinPre = minPre(root.getRight());
ArrayList<String> rootStrings = new ArrayList<>();
rootStrings.add(root.getVal());
MinPreFormat res = new MinPreFormat(rootStrings);
MinPreFormatComparator minPreFormatComparator = new MinPreFormatComparator();
if (LeftMinPre != null && RightMinPre != null) {
if ((root.getVal().equals("+") || root.getVal().equals("*"))
&& minPreFormatComparator.compare(LeftMinPre, RightMinPre) < 0) {
res.getVal().addAll(RightMinPre.getVal());
res.getVal().addAll(LeftMinPre.getVal());
} else {
res.getVal().addAll(LeftMinPre.getVal());
res.getVal().addAll(RightMinPre.getVal());
}
} else {
if (LeftMinPre != null) {
res.getVal().addAll(LeftMinPre.getVal());
}
if (RightMinPre != null) {
res.getVal().addAll(RightMinPre.getVal());
}
}
return res;
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手