Replace recursive evaluation with stacks.

I think recursion is undefined behavior in Rust.

1 files changed, 33 insertions, 4 deletions

diff --git a/src/expr.rs b/src/expr.rs
index 1022de4..bb6bb35 100644
--- a/src/expr.rs
+++ b/src/expr.rs
@@ -97,10 +97,39 @@ impl UnOp {
 
 impl Expr {
     pub fn eval(&self) -> Num {
-        match self {
-            Expr::Num(n) => *n,
-            Expr::UnOp { op, x } => op.eval(x.eval()),
-            Expr::BinOp { op, x, y } => op.eval(x.eval(), y.eval()),
+        enum Ex<'a> {
+            Expr(&'a Expr),
+            Un(UnOp),
+            Bin(BinOp),
+        }
+
+        let mut exprs = Vec::new();
+        let mut nums = Vec::new();
+
+        exprs.push(Ex::Expr(self));
+        while let Some(e) = exprs.pop() {
+            match e {
+                Ex::Expr(Expr::Num(n)) => nums.push(*n),
+                Ex::Expr(Expr::UnOp { op, x }) => {
+                    exprs.push(Ex::Un(*op));
+                    exprs.push(Ex::Expr(x));
+                }
+                Ex::Expr(Expr::BinOp { op, x, y }) => {
+                    exprs.push(Ex::Bin(*op));
+                    exprs.push(Ex::Expr(y));
+                    exprs.push(Ex::Expr(x));
+                }
+                Ex::Un(op) => {
+                    let n = nums.pop().unwrap();
+                    nums.push(op.eval(n));
+                }
+                Ex::Bin(op) => {
+                    let n2 = nums.pop().unwrap();
+                    let n1 = nums.pop().unwrap();
+                    nums.push(op.eval(n1, n2));
+                }
+            }
         }
+        nums[0]
     }
 }