ries_rs/
expr.rs

1//! Expression representation and manipulation
2//!
3//! Expressions are stored in postfix (reverse Polish) notation.
4
5use crate::symbol::{NumType, Seft, Symbol};
6use smallvec::SmallVec;
7use std::fmt;
8
9/// Maximum expression length (matching C version's MAX_ELEN)
10pub const MAX_EXPR_LEN: usize = 21;
11
12/// Output format for expression display
13#[derive(Debug, Clone, Copy, Default)]
14pub enum OutputFormat {
15    /// Default RIES format
16    #[default]
17    Default,
18    /// Pretty format with Unicode symbols (π, ℯ, φ, √)
19    Pretty,
20    /// Mathematica-compatible syntax
21    Mathematica,
22    /// SymPy Python syntax
23    SymPy,
24}
25
26impl OutputFormat {
27    /// Get the name for a symbol in this format
28    #[allow(dead_code)]
29    pub fn symbol_name(&self, sym: Symbol) -> &'static str {
30        use Symbol::*;
31        match self {
32            OutputFormat::Default => sym.name(),
33            OutputFormat::Pretty => match sym {
34                Pi => "π",
35                E => "ℯ",
36                Phi => "φ",
37                Sqrt => "√",
38                Square => "²",
39                Gamma => "γ",
40                Plastic => "ρ",
41                Catalan => "G",
42                _ => sym.name(),
43            },
44            OutputFormat::Mathematica => match sym {
45                Pi => "Pi",
46                E => "E",
47                Phi => "GoldenRatio",
48                Sqrt => "Sqrt",
49                Square => "²",
50                Ln => "Log",
51                Exp => "Exp",
52                SinPi => "Sin[Pi*",
53                CosPi => "Cos[Pi*",
54                TanPi => "Tan[Pi*",
55                LambertW => "ProductLog",
56                Gamma => "EulerGamma",
57                _ => sym.name(),
58            },
59            OutputFormat::SymPy => match sym {
60                Pi => "pi",
61                E => "E",
62                Phi => "GoldenRatio",
63                Sqrt => "sqrt",
64                Square => "²",
65                Ln => "log",
66                Exp => "exp",
67                SinPi => "sin(pi*",
68                CosPi => "cos(pi*",
69                TanPi => "tan(pi*",
70                LambertW => "lambertw",
71                Gamma => "EulerGamma",
72                _ => sym.name(),
73            },
74        }
75    }
76}
77
78/// A symbolic expression in postfix notation
79#[derive(Clone, PartialEq, Eq, Hash)]
80pub struct Expression {
81    /// Symbols in postfix order
82    symbols: SmallVec<[Symbol; MAX_EXPR_LEN]>,
83    /// Cached complexity score
84    complexity: u32,
85    /// Whether this expression contains the variable x
86    contains_x: bool,
87}
88
89impl Expression {
90    /// Create an empty expression
91    pub fn new() -> Self {
92        Self {
93            symbols: SmallVec::new(),
94            complexity: 0,
95            contains_x: false,
96        }
97    }
98
99    /// Create an expression from a slice of symbols
100    #[cfg(test)]
101    pub fn from_symbols(symbols: &[Symbol]) -> Self {
102        // Use saturating_add to prevent overflow with maliciously large weights
103        let complexity: u32 = symbols
104            .iter()
105            .map(|s| s.weight())
106            .fold(0u32, |acc, w| acc.saturating_add(w));
107        let contains_x = symbols.contains(&Symbol::X);
108        Self {
109            symbols: SmallVec::from_slice(symbols),
110            complexity,
111            contains_x,
112        }
113    }
114
115    /// Parse a well-formed postfix expression (e.g., "32s1+s*").
116    ///
117    /// This validates stack discipline while parsing, so malformed or incomplete
118    /// postfix strings return `None` instead of constructing an expression that
119    /// will later panic during formatting.
120    pub fn parse(s: &str) -> Option<Self> {
121        let mut symbols = SmallVec::new();
122        for b in s.bytes() {
123            symbols.push(Symbol::from_byte(b)?);
124        }
125        if !Self::is_valid_postfix(&symbols) {
126            return None;
127        }
128        // Use saturating_add to prevent overflow with maliciously large weights
129        let complexity: u32 = symbols
130            .iter()
131            .map(|s: &Symbol| s.weight())
132            .fold(0u32, |acc, w| acc.saturating_add(w));
133        let contains_x = symbols.contains(&Symbol::X);
134        Some(Self {
135            symbols,
136            complexity,
137            contains_x,
138        })
139    }
140
141    /// Get the symbols in this expression
142    #[inline]
143    pub fn symbols(&self) -> &[Symbol] {
144        &self.symbols
145    }
146
147    /// Get the expression length
148    #[inline]
149    pub fn len(&self) -> usize {
150        self.symbols.len()
151    }
152
153    /// Check if expression is empty
154    #[inline]
155    pub fn is_empty(&self) -> bool {
156        self.symbols.is_empty()
157    }
158
159    /// Get the complexity score
160    #[inline]
161    pub fn complexity(&self) -> u32 {
162        self.complexity
163    }
164
165    /// Check if this expression contains the variable x
166    #[inline]
167    pub fn contains_x(&self) -> bool {
168        self.contains_x
169    }
170
171    /// Count occurrences of a symbol in this expression.
172    #[inline]
173    pub fn count_symbol(&self, sym: Symbol) -> u32 {
174        self.symbols.iter().filter(|&&s| s == sym).count() as u32
175    }
176
177    /// Check if this is a valid complete expression (stack depth = 1)
178    ///
179    /// This method is part of the public API for external consumers who may want to
180    /// validate expressions before processing them.
181    #[allow(dead_code)]
182    pub fn is_valid(&self) -> bool {
183        Self::is_valid_postfix(&self.symbols)
184    }
185
186    fn is_valid_postfix(symbols: &[Symbol]) -> bool {
187        let mut depth: i32 = 0;
188        for sym in symbols {
189            match sym.seft() {
190                Seft::A => depth += 1,
191                Seft::B => { /* pop 1, push 1 - no change */ }
192                Seft::C => depth -= 1, // pop 2, push 1
193            }
194            if depth < 1 {
195                return false; // Stack underflow
196            }
197        }
198        depth == 1
199    }
200
201    /// Append a symbol to this expression
202    pub fn push(&mut self, sym: Symbol) {
203        // Use saturating_add to prevent overflow with many operations
204        self.complexity = self.complexity.saturating_add(sym.weight());
205        if sym == Symbol::X {
206            self.contains_x = true;
207        }
208        self.symbols.push(sym);
209    }
210
211    /// Remove the last symbol
212    pub fn pop(&mut self) -> Option<Symbol> {
213        let sym = self.symbols.pop()?;
214        // Use saturating_sub to prevent underflow (shouldn't happen with valid state)
215        self.complexity = self.complexity.saturating_sub(sym.weight());
216        // Recompute contains_x after popping
217        if sym == Symbol::X {
218            self.contains_x = self.symbols.contains(&Symbol::X);
219        }
220        Some(sym)
221    }
222
223    /// Append a symbol using a symbol table for weight lookup
224    ///
225    /// This is the table-driven version that uses per-run configuration
226    /// instead of global overrides.
227    pub fn push_with_table(&mut self, sym: Symbol, table: &crate::symbol_table::SymbolTable) {
228        // Use saturating_add to prevent overflow with many operations
229        self.complexity = self.complexity.saturating_add(table.weight(sym));
230        if sym == Symbol::X {
231            self.contains_x = true;
232        }
233        self.symbols.push(sym);
234    }
235
236    /// Remove the last symbol using a symbol table for weight lookup
237    ///
238    /// This is the table-driven version that uses per-run configuration
239    /// instead of global overrides.
240    pub fn pop_with_table(&mut self, table: &crate::symbol_table::SymbolTable) -> Option<Symbol> {
241        let sym = self.symbols.pop()?;
242        // Use saturating_sub to prevent underflow (shouldn't happen with valid state)
243        self.complexity = self.complexity.saturating_sub(table.weight(sym));
244        // Recompute contains_x after popping
245        if sym == Symbol::X {
246            self.contains_x = self.symbols.contains(&Symbol::X);
247        }
248        Some(sym)
249    }
250
251    /// Get the postfix string representation
252    pub fn to_postfix(&self) -> String {
253        self.symbols.iter().map(|s| *s as u8 as char).collect()
254    }
255
256    /// Convert to infix notation for display
257    ///
258    /// Uses proper operator precedence and associativity rules:
259    /// - Precedence levels (higher = tighter binding):
260    ///   - 100: Atoms (constants, x, function calls)
261    ///   - 9: Power (right-associative)
262    ///   - 7: Unary operators (negation, reciprocal)
263    ///   - 6: Multiplication, division
264    ///   - 5: Addition, subtraction
265    /// - Right-associative operators (power) bind right-to-left
266    /// - Left-associative operators bind left-to-right
267    pub fn to_infix(&self) -> String {
268        /// Precedence levels for operators
269        const PREC_ATOM: u8 = 100; // Constants, x, function calls
270        const PREC_POWER: u8 = 9; // ^ (right-associative)
271        const PREC_UNARY: u8 = 8; // Unary minus, reciprocal
272        const PREC_MUL: u8 = 6; // *, /
273        const PREC_ADD: u8 = 4; // +, -
274
275        /// Check if we need parentheses around an operand
276        /// parent_prec: precedence of the parent operator
277        /// child_prec: precedence of the child expression
278        /// is_right_assoc: true if parent is right-associative
279        /// is_right_operand: true if this is the right operand
280        fn needs_paren(
281            parent_prec: u8,
282            child_prec: u8,
283            is_right_assoc: bool,
284            is_right_operand: bool,
285        ) -> bool {
286            if child_prec < parent_prec {
287                return true;
288            }
289            // For right-associative operators, the right operand needs parens
290            // if it has the same precedence (e.g., a^(b^c) needs parens)
291            if is_right_assoc && is_right_operand && child_prec == parent_prec {
292                return true;
293            }
294            false
295        }
296
297        /// Wrap in parentheses if needed
298        fn maybe_paren_prec(
299            s: &str,
300            prec: u8,
301            parent_prec: u8,
302            is_right_assoc: bool,
303            is_right: bool,
304        ) -> String {
305            if needs_paren(parent_prec, prec, is_right_assoc, is_right) {
306                format!("({})", s)
307            } else {
308                s.to_string()
309            }
310        }
311
312        let mut stack: Vec<(String, u8)> = Vec::new(); // (string, precedence)
313
314        for &sym in &self.symbols {
315            match sym.seft() {
316                Seft::A => {
317                    stack.push((sym.display_name(), PREC_ATOM));
318                }
319                Seft::B => {
320                    let (arg, arg_prec) = stack
321                        .pop()
322                        .expect("stack underflow in to_infix: expression is not valid postfix");
323                    let result = match sym {
324                        Symbol::Neg => {
325                            // Negation needs parens around low-precedence expressions
326                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_UNARY, false, false);
327                            format!("-{}", arg_s)
328                        }
329                        Symbol::Recip => {
330                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_MUL, false, false);
331                            format!("1/{}", arg_s)
332                        }
333                        Symbol::Sqrt => format!("sqrt({})", arg),
334                        Symbol::Square => {
335                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_POWER, false, false);
336                            format!("{}^2", arg_s)
337                        }
338                        Symbol::Ln => format!("ln({})", arg),
339                        Symbol::Exp => {
340                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_POWER, true, true);
341                            format!("e^{}", arg_s)
342                        }
343                        Symbol::SinPi => format!("sinpi({})", arg),
344                        Symbol::CosPi => format!("cospi({})", arg),
345                        Symbol::TanPi => format!("tanpi({})", arg),
346                        Symbol::LambertW => format!("W({})", arg),
347                        Symbol::UserFunction0
348                        | Symbol::UserFunction1
349                        | Symbol::UserFunction2
350                        | Symbol::UserFunction3
351                        | Symbol::UserFunction4
352                        | Symbol::UserFunction5
353                        | Symbol::UserFunction6
354                        | Symbol::UserFunction7
355                        | Symbol::UserFunction8
356                        | Symbol::UserFunction9
357                        | Symbol::UserFunction10
358                        | Symbol::UserFunction11
359                        | Symbol::UserFunction12
360                        | Symbol::UserFunction13
361                        | Symbol::UserFunction14
362                        | Symbol::UserFunction15 => format!("{}({})", sym.display_name(), arg),
363                        _ => "?".to_string(),
364                    };
365                    stack.push((result, PREC_ATOM)); // Function calls are atomic
366                }
367                Seft::C => {
368                    let (b, b_prec) = stack
369                        .pop()
370                        .expect("stack underflow in to_infix: expression is not valid postfix");
371                    let (a, a_prec) = stack
372                        .pop()
373                        .expect("stack underflow in to_infix: expression is not valid postfix");
374                    let (result, prec) = match sym {
375                        Symbol::Add => {
376                            // Left operand never needs parens for left-associative +
377                            // Right operand needs parens if lower precedence
378                            let b_s = maybe_paren_prec(&b, b_prec, PREC_ADD, false, true);
379                            (format!("{}+{}", a, b_s), PREC_ADD)
380                        }
381                        Symbol::Sub => {
382                            // Right operand needs parens for - and +
383                            let b_s = maybe_paren_prec(&b, b_prec, PREC_ADD, false, true);
384                            (format!("{}-{}", a, b_s), PREC_ADD)
385                        }
386                        Symbol::Mul => {
387                            let a_s = maybe_paren_prec(&a, a_prec, PREC_MUL, false, false);
388                            let b_s = maybe_paren_prec(&b, b_prec, PREC_MUL, false, true);
389                            // Omit * in some cases: 2x instead of 2*x
390                            if a_s.chars().last().is_some_and(|c| c.is_ascii_digit())
391                                && b_s.chars().next().is_some_and(|c| c.is_alphabetic())
392                            {
393                                (format!("{} {}", a_s, b_s), PREC_MUL)
394                            } else {
395                                (format!("{}*{}", a_s, b_s), PREC_MUL)
396                            }
397                        }
398                        Symbol::Div => {
399                            let a_s = maybe_paren_prec(&a, a_prec, PREC_MUL, false, false);
400                            let b_s = maybe_paren_prec(&b, b_prec, PREC_MUL + 1, false, true);
401                            (format!("{}/{}", a_s, b_s), PREC_MUL)
402                        }
403                        Symbol::Pow => {
404                            // Power is right-associative: a^b^c = a^(b^c)
405                            // Left operand needs parens if lower precedence
406                            let a_s = maybe_paren_prec(&a, a_prec, PREC_POWER, true, false);
407                            // Right operand needs parens if same or lower precedence (due to right-assoc)
408                            let b_s = maybe_paren_prec(&b, b_prec, PREC_POWER, true, true);
409                            (format!("{}^{}", a_s, b_s), PREC_POWER)
410                        }
411                        Symbol::Root => (format!("{}\"/{}", a, b), PREC_POWER),
412                        Symbol::Log => (format!("log_{}({})", a, b), PREC_ATOM),
413                        Symbol::Atan2 => (format!("atan2({}, {})", a, b), PREC_ATOM),
414                        _ => unreachable!(),
415                    };
416                    stack.push((result, prec));
417                }
418            }
419        }
420
421        stack.pop().map(|(s, _)| s).unwrap_or_else(|| "?".into())
422    }
423
424    /// Convert to infix notation using a symbol table for display names
425    ///
426    /// This is the table-driven version that uses per-run configuration
427    /// instead of global overrides for symbol display names.
428    pub fn to_infix_with_table(&self, table: &crate::symbol_table::SymbolTable) -> String {
429        /// Precedence levels for operators
430        const PREC_ATOM: u8 = 100; // Constants, x, function calls
431        const PREC_POWER: u8 = 9; // ^ (right-associative)
432        const PREC_UNARY: u8 = 8; // Unary minus, reciprocal
433        const PREC_MUL: u8 = 6; // *, /
434        const PREC_ADD: u8 = 4; // +, -
435
436        /// Check if we need parentheses around an operand
437        fn needs_paren(
438            parent_prec: u8,
439            child_prec: u8,
440            is_right_assoc: bool,
441            is_right_operand: bool,
442        ) -> bool {
443            if child_prec < parent_prec {
444                return true;
445            }
446            if is_right_assoc && is_right_operand && child_prec == parent_prec {
447                return true;
448            }
449            false
450        }
451
452        /// Wrap in parentheses if needed
453        fn maybe_paren_prec(
454            s: &str,
455            prec: u8,
456            parent_prec: u8,
457            is_right_assoc: bool,
458            is_right: bool,
459        ) -> String {
460            if needs_paren(parent_prec, prec, is_right_assoc, is_right) {
461                format!("({})", s)
462            } else {
463                s.to_string()
464            }
465        }
466
467        let mut stack: Vec<(String, u8)> = Vec::new();
468
469        for &sym in &self.symbols {
470            match sym.seft() {
471                Seft::A => {
472                    stack.push((table.name(sym).to_string(), PREC_ATOM));
473                }
474                Seft::B => {
475                    let (arg, arg_prec) = stack
476                        .pop()
477                        .expect("stack underflow in to_infix: expression is not valid postfix");
478                    let result = match sym {
479                        Symbol::Neg => {
480                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_UNARY, false, false);
481                            format!("-{}", arg_s)
482                        }
483                        Symbol::Recip => {
484                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_MUL, false, false);
485                            format!("1/{}", arg_s)
486                        }
487                        Symbol::Sqrt => format!("sqrt({})", arg),
488                        Symbol::Square => {
489                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_POWER, false, false);
490                            format!("{}^2", arg_s)
491                        }
492                        Symbol::Ln => format!("ln({})", arg),
493                        Symbol::Exp => {
494                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_POWER, true, true);
495                            format!("e^{}", arg_s)
496                        }
497                        Symbol::SinPi => format!("sinpi({})", arg),
498                        Symbol::CosPi => format!("cospi({})", arg),
499                        Symbol::TanPi => format!("tanpi({})", arg),
500                        Symbol::LambertW => format!("W({})", arg),
501                        Symbol::UserFunction0
502                        | Symbol::UserFunction1
503                        | Symbol::UserFunction2
504                        | Symbol::UserFunction3
505                        | Symbol::UserFunction4
506                        | Symbol::UserFunction5
507                        | Symbol::UserFunction6
508                        | Symbol::UserFunction7
509                        | Symbol::UserFunction8
510                        | Symbol::UserFunction9
511                        | Symbol::UserFunction10
512                        | Symbol::UserFunction11
513                        | Symbol::UserFunction12
514                        | Symbol::UserFunction13
515                        | Symbol::UserFunction14
516                        | Symbol::UserFunction15 => format!("{}({})", table.name(sym), arg),
517                        _ => "?".to_string(),
518                    };
519                    stack.push((result, PREC_ATOM));
520                }
521                Seft::C => {
522                    let (b, b_prec) = stack
523                        .pop()
524                        .expect("stack underflow in to_infix: expression is not valid postfix");
525                    let (a, a_prec) = stack
526                        .pop()
527                        .expect("stack underflow in to_infix: expression is not valid postfix");
528                    let (result, prec) = match sym {
529                        Symbol::Add => {
530                            let b_s = maybe_paren_prec(&b, b_prec, PREC_ADD, false, true);
531                            (format!("{}+{}", a, b_s), PREC_ADD)
532                        }
533                        Symbol::Sub => {
534                            let b_s = maybe_paren_prec(&b, b_prec, PREC_ADD, false, true);
535                            (format!("{}-{}", a, b_s), PREC_ADD)
536                        }
537                        Symbol::Mul => {
538                            let a_s = maybe_paren_prec(&a, a_prec, PREC_MUL, false, false);
539                            let b_s = maybe_paren_prec(&b, b_prec, PREC_MUL, false, true);
540                            if a_s.chars().last().is_some_and(|c| c.is_ascii_digit())
541                                && b_s.chars().next().is_some_and(|c| c.is_alphabetic())
542                            {
543                                (format!("{} {}", a_s, b_s), PREC_MUL)
544                            } else {
545                                (format!("{}*{}", a_s, b_s), PREC_MUL)
546                            }
547                        }
548                        Symbol::Div => {
549                            let a_s = maybe_paren_prec(&a, a_prec, PREC_MUL, false, false);
550                            let b_s = maybe_paren_prec(&b, b_prec, PREC_MUL + 1, false, true);
551                            (format!("{}/{}", a_s, b_s), PREC_MUL)
552                        }
553                        Symbol::Pow => {
554                            let a_s = maybe_paren_prec(&a, a_prec, PREC_POWER, true, false);
555                            let b_s = maybe_paren_prec(&b, b_prec, PREC_POWER, true, true);
556                            (format!("{}^{}", a_s, b_s), PREC_POWER)
557                        }
558                        Symbol::Root => (format!("{}\"/{}", a, b), PREC_POWER),
559                        Symbol::Log => (format!("log_{}({})", a, b), PREC_ATOM),
560                        Symbol::Atan2 => (format!("atan2({}, {})", a, b), PREC_ATOM),
561                        _ => unreachable!(),
562                    };
563                    stack.push((result, prec));
564                }
565            }
566        }
567
568        stack.pop().map(|(s, _)| s).unwrap_or_else(|| "?".into())
569    }
570
571    /// Convert to infix notation with specified format
572    pub fn to_infix_with_format(&self, format: OutputFormat) -> String {
573        match format {
574            OutputFormat::Default => self.to_infix(),
575            OutputFormat::Pretty => {
576                let mut result = self.to_infix();
577                // Simple Unicode substitutions
578                result = result.replace("pi", "π");
579                result = result.replace("sqrt(", "√(");
580                result = result.replace("^2", "²");
581                result
582            }
583            OutputFormat::Mathematica => self.to_infix_mathematica(),
584            OutputFormat::SymPy => self.to_infix_sympy(),
585        }
586    }
587
588    /// Count the number of operators (non-atoms) in the expression
589    pub fn operator_count(&self) -> usize {
590        self.symbols
591            .iter()
592            .filter(|sym| sym.seft() != Seft::A)
593            .count()
594    }
595
596    /// Compute the maximum depth of the expression tree
597    pub fn tree_depth(&self) -> usize {
598        let mut stack: Vec<usize> = Vec::with_capacity(self.len());
599        for &sym in &self.symbols {
600            match sym.seft() {
601                Seft::A => stack.push(1),
602                Seft::B => {
603                    let Some(arg_depth) = stack.pop() else {
604                        return 0;
605                    };
606                    stack.push(arg_depth.saturating_add(1));
607                }
608                Seft::C => {
609                    let Some(rhs_depth) = stack.pop() else {
610                        return 0;
611                    };
612                    let Some(lhs_depth) = stack.pop() else {
613                        return 0;
614                    };
615                    stack.push(lhs_depth.max(rhs_depth).saturating_add(1));
616                }
617            }
618        }
619        if stack.len() == 1 {
620            stack[0]
621        } else {
622            0
623        }
624    }
625
626    fn to_infix_mathematica(&self) -> String {
627        let mut stack: Vec<String> = Vec::new();
628
629        for &sym in &self.symbols {
630            match sym.seft() {
631                Seft::A => {
632                    let s = match sym {
633                        Symbol::Pi => "Pi".to_string(),
634                        Symbol::E => "E".to_string(),
635                        Symbol::Phi => "GoldenRatio".to_string(),
636                        Symbol::Gamma => "EulerGamma".to_string(),
637                        _ => sym.display_name(),
638                    };
639                    stack.push(s);
640                }
641                Seft::B => {
642                    let arg = stack
643                        .pop()
644                        .expect("stack underflow in to_infix: expression is not valid postfix");
645                    let s = match sym {
646                        Symbol::Neg => format!("-({})", arg),
647                        Symbol::Recip => format!("1/({})", arg),
648                        Symbol::Sqrt => format!("Sqrt[{}]", arg),
649                        Symbol::Square => format!("({})^2", arg),
650                        Symbol::Ln => format!("Log[{}]", arg),
651                        Symbol::Exp => format!("Exp[{}]", arg),
652                        Symbol::SinPi => format!("Sin[Pi*({})]", arg),
653                        Symbol::CosPi => format!("Cos[Pi*({})]", arg),
654                        Symbol::TanPi => format!("Tan[Pi*({})]", arg),
655                        Symbol::LambertW => format!("ProductLog[{}]", arg),
656                        Symbol::UserFunction0
657                        | Symbol::UserFunction1
658                        | Symbol::UserFunction2
659                        | Symbol::UserFunction3
660                        | Symbol::UserFunction4
661                        | Symbol::UserFunction5
662                        | Symbol::UserFunction6
663                        | Symbol::UserFunction7
664                        | Symbol::UserFunction8
665                        | Symbol::UserFunction9
666                        | Symbol::UserFunction10
667                        | Symbol::UserFunction11
668                        | Symbol::UserFunction12
669                        | Symbol::UserFunction13
670                        | Symbol::UserFunction14
671                        | Symbol::UserFunction15 => format!("{}[{}]", sym.display_name(), arg),
672                        _ => "?".to_string(),
673                    };
674                    stack.push(s);
675                }
676                Seft::C => {
677                    let b = stack
678                        .pop()
679                        .expect("stack underflow in to_infix: expression is not valid postfix");
680                    let a = stack
681                        .pop()
682                        .expect("stack underflow in to_infix: expression is not valid postfix");
683                    let s = match sym {
684                        Symbol::Add => format!("({})+({})", a, b),
685                        Symbol::Sub => format!("({})-({})", a, b),
686                        Symbol::Mul => format!("({})*({})", a, b),
687                        Symbol::Div => format!("({})/({})", a, b),
688                        Symbol::Pow => format!("({})^({})", a, b),
689                        Symbol::Root => format!("({})^(1/({}))", b, a),
690                        Symbol::Log => format!("Log[{}, {}]", a, b),
691                        Symbol::Atan2 => format!("ArcTan[{}, {}]", b, a),
692                        _ => "?".to_string(),
693                    };
694                    stack.push(s);
695                }
696            }
697        }
698
699        stack.pop().unwrap_or_else(|| "?".to_string())
700    }
701
702    fn to_infix_sympy(&self) -> String {
703        let mut stack: Vec<String> = Vec::new();
704
705        for &sym in &self.symbols {
706            match sym.seft() {
707                Seft::A => {
708                    let s = match sym {
709                        Symbol::Pi => "pi".to_string(),
710                        Symbol::E => "E".to_string(),
711                        Symbol::Phi => "GoldenRatio".to_string(),
712                        Symbol::Gamma => "EulerGamma".to_string(),
713                        _ => sym.display_name(),
714                    };
715                    stack.push(s);
716                }
717                Seft::B => {
718                    let arg = stack
719                        .pop()
720                        .expect("stack underflow in to_infix: expression is not valid postfix");
721                    let s = match sym {
722                        Symbol::Neg => format!("-({})", arg),
723                        Symbol::Recip => format!("1/({})", arg),
724                        Symbol::Sqrt => format!("sqrt({})", arg),
725                        Symbol::Square => format!("({})**2", arg),
726                        Symbol::Ln => format!("log({})", arg),
727                        Symbol::Exp => format!("exp({})", arg),
728                        Symbol::SinPi => format!("sin(pi*({}))", arg),
729                        Symbol::CosPi => format!("cos(pi*({}))", arg),
730                        Symbol::TanPi => format!("tan(pi*({}))", arg),
731                        Symbol::LambertW => format!("lambertw({})", arg),
732                        Symbol::UserFunction0
733                        | Symbol::UserFunction1
734                        | Symbol::UserFunction2
735                        | Symbol::UserFunction3
736                        | Symbol::UserFunction4
737                        | Symbol::UserFunction5
738                        | Symbol::UserFunction6
739                        | Symbol::UserFunction7
740                        | Symbol::UserFunction8
741                        | Symbol::UserFunction9
742                        | Symbol::UserFunction10
743                        | Symbol::UserFunction11
744                        | Symbol::UserFunction12
745                        | Symbol::UserFunction13
746                        | Symbol::UserFunction14
747                        | Symbol::UserFunction15 => format!("{}({})", sym.display_name(), arg),
748                        _ => "?".to_string(),
749                    };
750                    stack.push(s);
751                }
752                Seft::C => {
753                    let b = stack
754                        .pop()
755                        .expect("stack underflow in to_infix: expression is not valid postfix");
756                    let a = stack
757                        .pop()
758                        .expect("stack underflow in to_infix: expression is not valid postfix");
759                    let s = match sym {
760                        Symbol::Add => format!("({})+({})", a, b),
761                        Symbol::Sub => format!("({})-({})", a, b),
762                        Symbol::Mul => format!("({})*({})", a, b),
763                        Symbol::Div => format!("({})/({})", a, b),
764                        Symbol::Pow => format!("({})**({})", a, b),
765                        Symbol::Root => format!("({})**(1/({}))", b, a),
766                        Symbol::Log => format!("log({}, {})", b, a),
767                        Symbol::Atan2 => format!("atan2({}, {})", a, b),
768                        _ => "?".to_string(),
769                    };
770                    stack.push(s);
771                }
772            }
773        }
774
775        stack.pop().unwrap_or_else(|| "?".to_string())
776    }
777}
778
779impl Default for Expression {
780    fn default() -> Self {
781        Self::new()
782    }
783}
784
785impl fmt::Display for Expression {
786    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
787        write!(f, "{}", self.to_infix())
788    }
789}
790
791impl fmt::Debug for Expression {
792    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
793        write!(f, "Expr[{}] = {}", self.to_postfix(), self.to_infix())
794    }
795}
796
797/// An evaluated expression with its numeric value
798#[derive(Clone, Debug)]
799pub struct EvaluatedExpr {
800    /// The symbolic expression
801    pub expr: Expression,
802    /// Computed value at x = target
803    pub value: f64,
804    /// Derivative with respect to x
805    pub derivative: f64,
806    /// Numeric type classification
807    ///
808    /// This field is part of the public API for library consumers who need
809    /// to track the numeric type of evaluated expressions.
810    #[allow(dead_code)]
811    pub num_type: NumType,
812}
813
814impl EvaluatedExpr {
815    pub fn new(expr: Expression, value: f64, derivative: f64, num_type: NumType) -> Self {
816        Self {
817            expr,
818            value,
819            derivative,
820            num_type,
821        }
822    }
823}
824
825#[cfg(test)]
826mod tests {
827    use super::*;
828
829    #[test]
830    fn test_parse_expression() {
831        let expr = Expression::parse("32+").unwrap();
832        assert_eq!(expr.len(), 3);
833        assert_eq!(expr.to_postfix(), "32+");
834        assert!(!expr.contains_x());
835    }
836
837    #[test]
838    fn test_expression_validity() {
839        // Valid: 3 2 + (pushes 3, pushes 2, adds them -> 1 value)
840        assert!(Expression::parse("32+").unwrap().is_valid());
841
842        // Valid: x 2 ^ (x squared)
843        assert!(Expression::parse("xs").unwrap().is_valid());
844
845        // Invalid: 3 + (not enough operands)
846        assert!(Expression::parse("3+").is_none());
847
848        // Invalid: 3 2 (two values left on stack)
849        assert!(Expression::parse("32").is_none());
850    }
851
852    #[test]
853    fn test_infix_conversion() {
854        assert_eq!(Expression::parse("32+").unwrap().to_infix(), "3+2");
855        assert_eq!(Expression::parse("32*").unwrap().to_infix(), "3*2");
856        assert_eq!(Expression::parse("xs").unwrap().to_infix(), "x^2");
857        assert_eq!(Expression::parse("xq").unwrap().to_infix(), "sqrt(x)");
858        assert_eq!(Expression::parse("32+5*").unwrap().to_infix(), "(3+2)*5");
859    }
860
861    #[test]
862    fn test_complexity() {
863        let expr = Expression::parse("xs").unwrap(); // x^2
864                                                     // x = 15, s (square) = 9
865        assert_eq!(expr.complexity(), 15 + 9);
866    }
867
868    #[test]
869    fn test_tree_depth_atom() {
870        // Single atom has depth 1
871        assert_eq!(Expression::parse("x").unwrap().tree_depth(), 1);
872        assert_eq!(Expression::parse("1").unwrap().tree_depth(), 1);
873        assert_eq!(Expression::parse("p").unwrap().tree_depth(), 1); // pi
874    }
875
876    #[test]
877    fn test_tree_depth_unary() {
878        // Unary op adds 1 to depth
879        assert_eq!(Expression::parse("xq").unwrap().tree_depth(), 2); // sqrt(x)
880        assert_eq!(Expression::parse("xs").unwrap().tree_depth(), 2); // x^2
881        assert_eq!(Expression::parse("xn").unwrap().tree_depth(), 2); // -x
882    }
883
884    #[test]
885    fn test_tree_depth_binary() {
886        // Binary op takes max of children + 1
887        assert_eq!(Expression::parse("12+").unwrap().tree_depth(), 2); // 1+2
888        assert_eq!(Expression::parse("x2*").unwrap().tree_depth(), 2); // x*2
889        assert_eq!(Expression::parse("x1+2*").unwrap().tree_depth(), 3); // (x+1)*2
890    }
891
892    #[test]
893    fn test_tree_depth_nested() {
894        // Deeply nested expressions
895        assert_eq!(Expression::parse("xqq").unwrap().tree_depth(), 3); // sqrt(sqrt(x))
896        assert_eq!(Expression::parse("12+34+*").unwrap().tree_depth(), 3); // (1+2)*(3+4)
897    }
898
899    #[test]
900    fn test_tree_depth_empty() {
901        // Empty expression has depth 0
902        assert_eq!(Expression::new().tree_depth(), 0);
903    }
904
905    #[test]
906    fn test_tree_depth_malformed() {
907        // Malformed expressions return 0
908        assert_eq!(
909            Expression::from_symbols(&[Symbol::X, Symbol::One]).tree_depth(),
910            0
911        );
912    }
913
914    #[test]
915    fn test_operator_count_atom() {
916        // Single atom has no operators
917        assert_eq!(Expression::parse("x").unwrap().operator_count(), 0);
918        assert_eq!(Expression::parse("1").unwrap().operator_count(), 0);
919        assert_eq!(Expression::parse("p").unwrap().operator_count(), 0);
920    }
921
922    #[test]
923    fn test_operator_count_unary() {
924        // Unary op counts as 1 operator
925        assert_eq!(Expression::parse("xq").unwrap().operator_count(), 1);
926        assert_eq!(Expression::parse("xs").unwrap().operator_count(), 1);
927        assert_eq!(Expression::parse("xn").unwrap().operator_count(), 1);
928    }
929
930    #[test]
931    fn test_operator_count_binary() {
932        // Binary op counts as 1 operator
933        assert_eq!(Expression::parse("12+").unwrap().operator_count(), 1);
934        assert_eq!(Expression::parse("x2*").unwrap().operator_count(), 1);
935    }
936
937    #[test]
938    fn test_operator_count_complex() {
939        // Multiple operators
940        assert_eq!(Expression::parse("x1+2*").unwrap().operator_count(), 2); // (x+1)*2
941        assert_eq!(Expression::parse("xq1+").unwrap().operator_count(), 2); // sqrt(x)+1
942        assert_eq!(Expression::parse("12+34+*").unwrap().operator_count(), 3); // (1+2)*(3+4)
943    }
944
945    #[test]
946    fn test_operator_count_empty() {
947        assert_eq!(Expression::new().operator_count(), 0);
948    }
949
950    #[test]
951    fn test_push_pop_complexity_saturating() {
952        let mut expr = Expression::new();
953
954        // Push should use saturating_add
955        for _ in 0..1000 {
956            expr.push(Symbol::X);
957        }
958        // Complexity should saturate, not overflow
959        assert!(expr.complexity() < u32::MAX);
960
961        // Pop should use saturating_sub
962        for _ in 0..1000 {
963            expr.pop();
964        }
965        // Should be back to 0 without underflow
966        assert_eq!(expr.complexity(), 0);
967    }
968
969    /// Issue 6: to_infix must not silently produce '?' for invalid expressions.
970    /// Instead, stack underflow in the mid-loop pops is a programming error and
971    /// should panic with a clear message via expect().
972    #[test]
973    #[should_panic(expected = "stack underflow in to_infix")]
974    fn test_to_infix_panics_on_malformed_expression() {
975        // An expression with only a binary operator has no operands — stack underflows
976        // on the first pop inside the loop. from_symbols bypasses parse validation.
977        let expr = Expression::from_symbols(&[Symbol::Add]);
978        let _ = expr.to_infix();
979    }
980}
ries_rs/expr.rs

ries_rs/
expr.rs
