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

ries_rs/
expr.rs
