我正在为 BigIntegers(只有 *、^ 和 !)编写波兰语记数法计算器,我得到一个 OutOfMemoryError
在我减去 BigInteger.ONE
的那一行让阶乘起作用,为什么?
package polish_calculator;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Stack;
public class Main {
static BigInteger factorial(BigInteger number){
Stack <BigInteger> factorialStack = new Stack<BigInteger>();
factorialStack.push(number);
while (!number.equals(BigInteger.ONE)){ //load the stack
factorialStack.push(number.subtract(BigInteger.ONE)); // here's the error
}
BigInteger result = BigInteger.ONE;
while(!factorialStack.empty()){ // empty and multiply the stack
result.multiply(factorialStack.pop());
}
return result;
}
public static void main(String[] args) throws IOException {
BigInteger testFactorial = new BigInteger("12");
System.out.println(factorial(testFactorial));
Stack <String> stack = new Stack<String>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String readExpression = br.readLine();
while(!readExpression.equals("")){
String [] splittedExpression = readExpression.split(" ");
for(int i=0; i<splittedExpression.length;i++){
if(splittedExpression[i].equals("*"))
{
BigInteger operand1 = new BigInteger(stack.pop());
BigInteger operand2 = new BigInteger(stack.pop());
BigInteger result = operand1.multiply(operand2);
String stackString = result.toString();
stack.push(stackString);
}
if(splittedExpression[i].equals("^"))
{
BigInteger operand1 = new BigInteger(stack.pop());
BigInteger operand2 = new BigInteger(stack.pop());
BigInteger result = operand1.modPow(operand2, BigInteger.ONE);
String stackString = result.toString();
stack.push(stackString);
}
if(splittedExpression[i].equals("!"))
{
BigInteger operand1 = new BigInteger(stack.pop());
BigInteger result = factorial(operand1);
String stackString = result.toString();
stack.push(stackString);
}
else{ //it's an integer
stack.push(splittedExpression[i]);
}
} // end for splittedExpression.length
}
}
}
错误:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.math.BigInteger.subtract(BigInteger.java:1118)
at polish_calculator.Main.factorial(Main.java:45)
at polish_calculator.Main.main(Main.java:65)
Java Result: 1
最佳答案
BigInteger.subtract 生成一个新的 BigInteger,您将其压入堆栈。
但原始数字仍然相同,因此条件 !number.equals(BigInteger.ONE) 永远不会为真。
所以你用 number-1 的副本永远填充堆栈,直到你用完内存
编辑(再次):
请注意,这也是一种非常耗费内存的计算阶乘的方法,因为您需要将 N 个值压入堆栈才能计算 N!在进行过程中将它们相乘会更好,尽管在阶乘确实变得非常大之前当然不需要很大的 N。
参见 http://en.wikipedia.org/wiki/Factorial有关有效计算大阶乘的一些详细信息。
关于java - BigInteger 上的 OutOfMemoryError,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6003121/