Skip to content

Instantly share code, notes, and snippets.

@qiuwei
Created June 22, 2017 15:39
Show Gist options
  • Save qiuwei/e58791599f768337e89ba8a621c26bdc to your computer and use it in GitHub Desktop.
Save qiuwei/e58791599f768337e89ba8a621c26bdc to your computer and use it in GitHub Desktop.
Factorial with stack
class Frame {
int number;
int answer;
boolean done;
public Frame(int number, int answer, boolean done){
this.number = number;
this.answer = answer;
this.done = done;
}
}
public class Solution{
Stack<Frame> stack = new Stack<>();
//@param root: The root of binary tree.
int fact(int n) {
stack.push(new Frame(n, 0, false));
Frame f = stack.peek();
while(!stack.empty()) {
if(f.done) {
System.out.println("Popping " + f.number);
stack.pop();
if(!stack.empty()) {
stack.peek().answer = f.answer * stack.peek().number;
stack.peek().done = true;
}
} else {
int number = f.number;
if(number == 0) {
System.out.println("Return from " + number);
stack.peek().answer = 1;
stack.peek().done = true;
} else {
System.out.println("Push " + (number - 1));
stack.push(new Frame(number-1, 0, false));
}
}
if (! stack.empty()) {
f = stack.peek();
}
}
return f.answer;
}
public static void main(String[] args) {
System.out.println("Result: " + new Solution().fact(10));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment