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    /// Convert to infix notation using a symbol table for display names
362    ///
363    /// This is the table-driven version that uses per-run configuration
364    /// instead of global overrides for symbol display names.
365    pub fn to_infix_with_table(&self, table: &crate::symbol_table::SymbolTable) -> String {
366        /// Precedence levels for operators
367        const PREC_ATOM: u8 = 100; // Constants, x, function calls
368        const PREC_POWER: u8 = 9; // ^ (right-associative)
369        const PREC_UNARY: u8 = 8; // Unary minus, reciprocal
370        const PREC_MUL: u8 = 6; // *, /
371        const PREC_ADD: u8 = 4; // +, -
372
373        /// Check if we need parentheses around an operand
374        fn needs_paren(
375            parent_prec: u8,
376            child_prec: u8,
377            is_right_assoc: bool,
378            is_right_operand: bool,
379        ) -> bool {
380            if child_prec < parent_prec {
381                return true;
382            }
383            if is_right_assoc && is_right_operand && child_prec == parent_prec {
384                return true;
385            }
386            false
387        }
388
389        /// Wrap in parentheses if needed
390        fn maybe_paren_prec(
391            s: &str,
392            prec: u8,
393            parent_prec: u8,
394            is_right_assoc: bool,
395            is_right: bool,
396        ) -> String {
397            if needs_paren(parent_prec, prec, is_right_assoc, is_right) {
398                format!("({})", s)
399            } else {
400                s.to_string()
401            }
402        }
403
404        let mut stack: Vec<(String, u8)> = Vec::new();
405
406        for &sym in &self.symbols {
407            match sym.seft() {
408                Seft::A => {
409                    stack.push((table.name(sym).to_string(), PREC_ATOM));
410                }
411                Seft::B => {
412                    let (arg, arg_prec) = stack
413                        .pop()
414                        .expect("stack underflow in to_infix: expression is not valid postfix");
415                    let result = match sym {
416                        Symbol::Neg => {
417                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_UNARY, false, false);
418                            format!("-{}", arg_s)
419                        }
420                        Symbol::Recip => {
421                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_MUL, false, false);
422                            format!("1/{}", arg_s)
423                        }
424                        Symbol::Sqrt => format!("sqrt({})", arg),
425                        Symbol::Square => {
426                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_POWER, false, false);
427                            format!("{}^2", arg_s)
428                        }
429                        Symbol::Ln => format!("ln({})", arg),
430                        Symbol::Exp => {
431                            let arg_s = maybe_paren_prec(&arg, arg_prec, PREC_POWER, true, true);
432                            format!("e^{}", arg_s)
433                        }
434                        Symbol::SinPi => format!("sinpi({})", arg),
435                        Symbol::CosPi => format!("cospi({})", arg),
436                        Symbol::TanPi => format!("tanpi({})", arg),
437                        Symbol::LambertW => format!("W({})", arg),
438                        Symbol::UserFunction0
439                        | Symbol::UserFunction1
440                        | Symbol::UserFunction2
441                        | Symbol::UserFunction3
442                        | Symbol::UserFunction4
443                        | Symbol::UserFunction5
444                        | Symbol::UserFunction6
445                        | Symbol::UserFunction7
446                        | Symbol::UserFunction8
447                        | Symbol::UserFunction9
448                        | Symbol::UserFunction10
449                        | Symbol::UserFunction11
450                        | Symbol::UserFunction12
451                        | Symbol::UserFunction13
452                        | Symbol::UserFunction14
453                        | Symbol::UserFunction15 => format!("{}({})", table.name(sym), arg),
454                        _ => "?".to_string(),
455                    };
456                    stack.push((result, PREC_ATOM));
457                }
458                Seft::C => {
459                    let (b, b_prec) = stack
460                        .pop()
461                        .expect("stack underflow in to_infix: expression is not valid postfix");
462                    let (a, a_prec) = stack
463                        .pop()
464                        .expect("stack underflow in to_infix: expression is not valid postfix");
465                    let (result, prec) = match sym {
466                        Symbol::Add => {
467                            let b_s = maybe_paren_prec(&b, b_prec, PREC_ADD, false, true);
468                            (format!("{}+{}", a, b_s), PREC_ADD)
469                        }
470                        Symbol::Sub => {
471                            let b_s = maybe_paren_prec(&b, b_prec, PREC_ADD, false, true);
472                            (format!("{}-{}", a, b_s), PREC_ADD)
473                        }
474                        Symbol::Mul => {
475                            let a_s = maybe_paren_prec(&a, a_prec, PREC_MUL, false, false);
476                            let b_s = maybe_paren_prec(&b, b_prec, PREC_MUL, false, true);
477                            if a_s.chars().last().is_some_and(|c| c.is_ascii_digit())
478                                && b_s.chars().next().is_some_and(|c| c.is_alphabetic())
479                            {
480                                (format!("{} {}", a_s, b_s), PREC_MUL)
481                            } else {
482                                (format!("{}*{}", a_s, b_s), PREC_MUL)
483                            }
484                        }
485                        Symbol::Div => {
486                            let a_s = maybe_paren_prec(&a, a_prec, PREC_MUL, false, false);
487                            let b_s = maybe_paren_prec(&b, b_prec, PREC_MUL + 1, false, true);
488                            (format!("{}/{}", a_s, b_s), PREC_MUL)
489                        }
490                        Symbol::Pow => {
491                            let a_s = maybe_paren_prec(&a, a_prec, PREC_POWER, true, false);
492                            let b_s = maybe_paren_prec(&b, b_prec, PREC_POWER, true, true);
493                            (format!("{}^{}", a_s, b_s), PREC_POWER)
494                        }
495                        Symbol::Root => (format!("{}\"/{}", a, b), PREC_POWER),
496                        Symbol::Log => (format!("log_{}({})", a, b), PREC_ATOM),
497                        Symbol::Atan2 => (format!("atan2({}, {})", a, b), PREC_ATOM),
498                        _ => unreachable!(),
499                    };
500                    stack.push((result, prec));
501                }
502            }
503        }
504
505        stack.pop().map(|(s, _)| s).unwrap_or_else(|| "?".into())
506    }
507
508    /// Convert to infix notation with specified format
509    pub fn to_infix_with_format(&self, format: OutputFormat) -> String {
510        match format {
511            OutputFormat::Default => self.to_infix(),
512            OutputFormat::Pretty => {
513                let mut result = self.to_infix();
514                // Simple Unicode substitutions
515                result = result.replace("pi", "π");
516                result = result.replace("sqrt(", "√(");
517                result = result.replace("^2", "²");
518                result
519            }
520            OutputFormat::Mathematica => self.to_infix_mathematica(),
521            OutputFormat::SymPy => self.to_infix_sympy(),
522        }
523    }
524
525    /// Count the number of operators (non-atoms) in the expression
526    pub fn operator_count(&self) -> usize {
527        self.symbols
528            .iter()
529            .filter(|sym| sym.seft() != Seft::A)
530            .count()
531    }
532
533    /// Compute the maximum depth of the expression tree
534    pub fn tree_depth(&self) -> usize {
535        let mut stack: Vec<usize> = Vec::with_capacity(self.len());
536        for &sym in &self.symbols {
537            match sym.seft() {
538                Seft::A => stack.push(1),
539                Seft::B => {
540                    let Some(arg_depth) = stack.pop() else {
541                        return 0;
542                    };
543                    stack.push(arg_depth.saturating_add(1));
544                }
545                Seft::C => {
546                    let Some(rhs_depth) = stack.pop() else {
547                        return 0;
548                    };
549                    let Some(lhs_depth) = stack.pop() else {
550                        return 0;
551                    };
552                    stack.push(lhs_depth.max(rhs_depth).saturating_add(1));
553                }
554            }
555        }
556        if stack.len() == 1 {
557            stack[0]
558        } else {
559            0
560        }
561    }
562
563    pub fn to_infix_mathematica(&self) -> String {
564        const PREC_ATOM: u8 = 100;
565        const PREC_POWER: u8 = 9;
566        const PREC_UNARY: u8 = 8;
567        const PREC_MUL: u8 = 6;
568        const PREC_ADD: u8 = 4;
569
570        fn needs_paren(
571            parent_prec: u8,
572            child_prec: u8,
573            is_right_assoc: bool,
574            is_right_operand: bool,
575        ) -> bool {
576            if child_prec < parent_prec {
577                return true;
578            }
579            if is_right_assoc && is_right_operand && child_prec == parent_prec {
580                return true;
581            }
582            false
583        }
584
585        fn maybe_paren(
586            s: &str,
587            prec: u8,
588            parent_prec: u8,
589            is_right_assoc: bool,
590            is_right: bool,
591        ) -> String {
592            if needs_paren(parent_prec, prec, is_right_assoc, is_right) {
593                format!("({})", s)
594            } else {
595                s.to_string()
596            }
597        }
598
599        let mut stack: Vec<(String, u8)> = Vec::new();
600
601        for &sym in &self.symbols {
602            match sym.seft() {
603                Seft::A => {
604                    let s = match sym {
605                        Symbol::Pi => "Pi",
606                        Symbol::E => "E",
607                        Symbol::Phi => "GoldenRatio",
608                        Symbol::Gamma => "EulerGamma",
609                        Symbol::Apery => "Zeta[3]",
610                        Symbol::Catalan => "Catalan",
611                        _ => "",
612                    };
613                    let name = if s.is_empty() {
614                        sym.display_name()
615                    } else {
616                        s.to_string()
617                    };
618                    stack.push((name, PREC_ATOM));
619                }
620                Seft::B => {
621                    let (arg, arg_prec) = stack
622                        .pop()
623                        .expect("stack underflow in to_infix: expression is not valid postfix");
624                    let result = match sym {
625                        Symbol::Neg => {
626                            let s = maybe_paren(&arg, arg_prec, PREC_UNARY, false, false);
627                            format!("-{}", s)
628                        }
629                        Symbol::Recip => {
630                            let s = maybe_paren(&arg, arg_prec, PREC_MUL, false, false);
631                            format!("1/{}", s)
632                        }
633                        Symbol::Sqrt => format!("Sqrt[{}]", arg),
634                        Symbol::Square => {
635                            let s = maybe_paren(&arg, arg_prec, PREC_POWER, false, false);
636                            format!("{}^2", s)
637                        }
638                        Symbol::Ln => format!("Log[{}]", arg),
639                        Symbol::Exp => format!("Exp[{}]", arg),
640                        Symbol::SinPi => format!("Sin[Pi*{}]", arg),
641                        Symbol::CosPi => format!("Cos[Pi*{}]", arg),
642                        Symbol::TanPi => format!("Tan[Pi*{}]", arg),
643                        Symbol::LambertW => format!("ProductLog[{}]", arg),
644                        Symbol::UserFunction0
645                        | Symbol::UserFunction1
646                        | Symbol::UserFunction2
647                        | Symbol::UserFunction3
648                        | Symbol::UserFunction4
649                        | Symbol::UserFunction5
650                        | Symbol::UserFunction6
651                        | Symbol::UserFunction7
652                        | Symbol::UserFunction8
653                        | Symbol::UserFunction9
654                        | Symbol::UserFunction10
655                        | Symbol::UserFunction11
656                        | Symbol::UserFunction12
657                        | Symbol::UserFunction13
658                        | Symbol::UserFunction14
659                        | Symbol::UserFunction15 => format!("{}[{}]", sym.display_name(), arg),
660                        _ => "?".to_string(),
661                    };
662                    stack.push((result, PREC_ATOM));
663                }
664                Seft::C => {
665                    let (b, b_prec) = stack
666                        .pop()
667                        .expect("stack underflow in to_infix: expression is not valid postfix");
668                    let (a, a_prec) = stack
669                        .pop()
670                        .expect("stack underflow in to_infix: expression is not valid postfix");
671                    let (result, prec) = match sym {
672                        Symbol::Add => {
673                            let b_s = maybe_paren(&b, b_prec, PREC_ADD, false, true);
674                            (format!("{}+{}", a, b_s), PREC_ADD)
675                        }
676                        Symbol::Sub => {
677                            let b_s = maybe_paren(&b, b_prec, PREC_ADD, false, true);
678                            (format!("{}-{}", a, b_s), PREC_ADD)
679                        }
680                        Symbol::Mul => {
681                            let a_s = maybe_paren(&a, a_prec, PREC_MUL, false, false);
682                            let b_s = maybe_paren(&b, b_prec, PREC_MUL, false, true);
683                            (format!("{}*{}", a_s, b_s), PREC_MUL)
684                        }
685                        Symbol::Div => {
686                            let a_s = maybe_paren(&a, a_prec, PREC_MUL, false, false);
687                            let b_s = maybe_paren(&b, b_prec, PREC_MUL + 1, false, true);
688                            (format!("{}/{}", a_s, b_s), PREC_MUL)
689                        }
690                        Symbol::Pow => {
691                            let a_s = maybe_paren(&a, a_prec, PREC_POWER, true, false);
692                            let b_s = maybe_paren(&b, b_prec, PREC_POWER, true, true);
693                            (format!("{}^{}", a_s, b_s), PREC_POWER)
694                        }
695                        Symbol::Root => {
696                            let b_s = maybe_paren(&b, b_prec, PREC_POWER, true, false);
697                            (format!("{}^(1/{})", b_s, a), PREC_POWER)
698                        }
699                        Symbol::Log => (format!("Log[{}, {}]", a, b), PREC_ATOM),
700                        Symbol::Atan2 => (format!("ArcTan[{}, {}]", b, a), PREC_ATOM),
701                        _ => unreachable!(),
702                    };
703                    stack.push((result, prec));
704                }
705            }
706        }
707
708        stack
709            .pop()
710            .map(|(s, _)| s)
711            .unwrap_or_else(|| "?".to_string())
712    }
713
714    pub fn to_infix_sympy(&self) -> String {
715        const PREC_ATOM: u8 = 100;
716        const PREC_POWER: u8 = 9;
717        const PREC_UNARY: u8 = 8;
718        const PREC_MUL: u8 = 6;
719        const PREC_ADD: u8 = 4;
720
721        fn needs_paren(
722            parent_prec: u8,
723            child_prec: u8,
724            is_right_assoc: bool,
725            is_right_operand: bool,
726        ) -> bool {
727            if child_prec < parent_prec {
728                return true;
729            }
730            if is_right_assoc && is_right_operand && child_prec == parent_prec {
731                return true;
732            }
733            false
734        }
735
736        fn maybe_paren(
737            s: &str,
738            prec: u8,
739            parent_prec: u8,
740            is_right_assoc: bool,
741            is_right: bool,
742        ) -> String {
743            if needs_paren(parent_prec, prec, is_right_assoc, is_right) {
744                format!("({})", s)
745            } else {
746                s.to_string()
747            }
748        }
749
750        let mut stack: Vec<(String, u8)> = Vec::new();
751
752        for &sym in &self.symbols {
753            match sym.seft() {
754                Seft::A => {
755                    let s = match sym {
756                        Symbol::Pi => "pi",
757                        Symbol::E => "E",
758                        Symbol::Phi => "GoldenRatio",
759                        Symbol::Gamma => "EulerGamma",
760                        Symbol::Apery => "zeta(3)",
761                        Symbol::Catalan => "Catalan",
762                        _ => "",
763                    };
764                    let name = if s.is_empty() {
765                        sym.display_name()
766                    } else {
767                        s.to_string()
768                    };
769                    stack.push((name, PREC_ATOM));
770                }
771                Seft::B => {
772                    let (arg, arg_prec) = stack
773                        .pop()
774                        .expect("stack underflow in to_infix: expression is not valid postfix");
775                    let result = match sym {
776                        Symbol::Neg => {
777                            let s = maybe_paren(&arg, arg_prec, PREC_UNARY, false, false);
778                            format!("-{}", s)
779                        }
780                        Symbol::Recip => {
781                            let s = maybe_paren(&arg, arg_prec, PREC_MUL, false, false);
782                            format!("1/{}", s)
783                        }
784                        Symbol::Sqrt => format!("sqrt({})", arg),
785                        Symbol::Square => {
786                            let s = maybe_paren(&arg, arg_prec, PREC_POWER, false, false);
787                            format!("{}**2", s)
788                        }
789                        Symbol::Ln => format!("log({})", arg),
790                        Symbol::Exp => format!("exp({})", arg),
791                        Symbol::SinPi => format!("sin(pi*{})", arg),
792                        Symbol::CosPi => format!("cos(pi*{})", arg),
793                        Symbol::TanPi => format!("tan(pi*{})", arg),
794                        Symbol::LambertW => format!("lambertw({})", arg),
795                        Symbol::UserFunction0
796                        | Symbol::UserFunction1
797                        | Symbol::UserFunction2
798                        | Symbol::UserFunction3
799                        | Symbol::UserFunction4
800                        | Symbol::UserFunction5
801                        | Symbol::UserFunction6
802                        | Symbol::UserFunction7
803                        | Symbol::UserFunction8
804                        | Symbol::UserFunction9
805                        | Symbol::UserFunction10
806                        | Symbol::UserFunction11
807                        | Symbol::UserFunction12
808                        | Symbol::UserFunction13
809                        | Symbol::UserFunction14
810                        | Symbol::UserFunction15 => format!("{}({})", sym.display_name(), arg),
811                        _ => "?".to_string(),
812                    };
813                    stack.push((result, PREC_ATOM));
814                }
815                Seft::C => {
816                    let (b, b_prec) = stack
817                        .pop()
818                        .expect("stack underflow in to_infix: expression is not valid postfix");
819                    let (a, a_prec) = stack
820                        .pop()
821                        .expect("stack underflow in to_infix: expression is not valid postfix");
822                    let (result, prec) = match sym {
823                        Symbol::Add => {
824                            let b_s = maybe_paren(&b, b_prec, PREC_ADD, false, true);
825                            (format!("{}+{}", a, b_s), PREC_ADD)
826                        }
827                        Symbol::Sub => {
828                            let b_s = maybe_paren(&b, b_prec, PREC_ADD, false, true);
829                            (format!("{}-{}", a, b_s), PREC_ADD)
830                        }
831                        Symbol::Mul => {
832                            let a_s = maybe_paren(&a, a_prec, PREC_MUL, false, false);
833                            let b_s = maybe_paren(&b, b_prec, PREC_MUL, false, true);
834                            (format!("{}*{}", a_s, b_s), PREC_MUL)
835                        }
836                        Symbol::Div => {
837                            let a_s = maybe_paren(&a, a_prec, PREC_MUL, false, false);
838                            let b_s = maybe_paren(&b, b_prec, PREC_MUL + 1, false, true);
839                            (format!("{}/{}", a_s, b_s), PREC_MUL)
840                        }
841                        Symbol::Pow => {
842                            let a_s = maybe_paren(&a, a_prec, PREC_POWER, true, false);
843                            let b_s = maybe_paren(&b, b_prec, PREC_POWER, true, true);
844                            (format!("{}**{}", a_s, b_s), PREC_POWER)
845                        }
846                        Symbol::Root => {
847                            let b_s = maybe_paren(&b, b_prec, PREC_POWER, true, false);
848                            (format!("{}**(1/{})", b_s, a), PREC_POWER)
849                        }
850                        Symbol::Log => (format!("log({}, {})", b, a), PREC_ATOM),
851                        Symbol::Atan2 => (format!("atan2({}, {})", a, b), PREC_ATOM),
852                        _ => unreachable!(),
853                    };
854                    stack.push((result, prec));
855                }
856            }
857        }
858
859        stack
860            .pop()
861            .map(|(s, _)| s)
862            .unwrap_or_else(|| "?".to_string())
863    }
864}
865
866impl Default for Expression {
867    fn default() -> Self {
868        Self::new()
869    }
870}
871
872impl fmt::Display for Expression {
873    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
874        write!(f, "{}", self.to_infix())
875    }
876}
877
878impl fmt::Debug for Expression {
879    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
880        write!(f, "Expr[{}] = {}", self.to_postfix(), self.to_infix())
881    }
882}
883
884/// An evaluated expression with its numeric value
885#[derive(Clone, Debug)]
886pub struct EvaluatedExpr {
887    /// The symbolic expression
888    pub expr: Expression,
889    /// Computed value at x = target
890    pub value: f64,
891    /// Derivative with respect to x
892    pub derivative: f64,
893    /// Numeric type classification
894    ///
895    /// This field is part of the public API for library consumers who need
896    /// to track the numeric type of evaluated expressions.
897    #[allow(dead_code)]
898    pub num_type: NumType,
899}
900
901impl EvaluatedExpr {
902    pub fn new(expr: Expression, value: f64, derivative: f64, num_type: NumType) -> Self {
903        Self {
904            expr,
905            value,
906            derivative,
907            num_type,
908        }
909    }
910}
911
912#[cfg(test)]
913mod tests {
914    use super::*;
915
916    #[test]
917    fn test_parse_expression() {
918        let expr = Expression::parse("32+").unwrap();
919        assert_eq!(expr.len(), 3);
920        assert_eq!(expr.to_postfix(), "32+");
921        assert!(!expr.contains_x());
922    }
923
924    #[test]
925    fn test_expression_validity() {
926        // Valid: 3 2 + (pushes 3, pushes 2, adds them -> 1 value)
927        assert!(Expression::parse("32+").unwrap().is_valid());
928
929        // Valid: x 2 ^ (x squared)
930        assert!(Expression::parse("xs").unwrap().is_valid());
931
932        // Invalid: 3 + (not enough operands)
933        assert!(Expression::parse("3+").is_none());
934
935        // Invalid: 3 2 (two values left on stack)
936        assert!(Expression::parse("32").is_none());
937    }
938
939    #[test]
940    fn test_infix_conversion() {
941        assert_eq!(Expression::parse("32+").unwrap().to_infix(), "3+2");
942        assert_eq!(Expression::parse("32*").unwrap().to_infix(), "3*2");
943        assert_eq!(Expression::parse("xs").unwrap().to_infix(), "x^2");
944        assert_eq!(Expression::parse("xq").unwrap().to_infix(), "sqrt(x)");
945        assert_eq!(Expression::parse("32+5*").unwrap().to_infix(), "(3+2)*5");
946    }
947
948    #[test]
949    fn test_complexity() {
950        let expr = Expression::parse("xs").unwrap(); // x^2
951                                                     // x = 15, s (square) = 9
952        assert_eq!(expr.complexity(), 15 + 9);
953    }
954
955    #[test]
956    fn test_tree_depth_atom() {
957        // Single atom has depth 1
958        assert_eq!(Expression::parse("x").unwrap().tree_depth(), 1);
959        assert_eq!(Expression::parse("1").unwrap().tree_depth(), 1);
960        assert_eq!(Expression::parse("p").unwrap().tree_depth(), 1); // pi
961    }
962
963    #[test]
964    fn test_tree_depth_unary() {
965        // Unary op adds 1 to depth
966        assert_eq!(Expression::parse("xq").unwrap().tree_depth(), 2); // sqrt(x)
967        assert_eq!(Expression::parse("xs").unwrap().tree_depth(), 2); // x^2
968        assert_eq!(Expression::parse("xn").unwrap().tree_depth(), 2); // -x
969    }
970
971    #[test]
972    fn test_tree_depth_binary() {
973        // Binary op takes max of children + 1
974        assert_eq!(Expression::parse("12+").unwrap().tree_depth(), 2); // 1+2
975        assert_eq!(Expression::parse("x2*").unwrap().tree_depth(), 2); // x*2
976        assert_eq!(Expression::parse("x1+2*").unwrap().tree_depth(), 3); // (x+1)*2
977    }
978
979    #[test]
980    fn test_tree_depth_nested() {
981        // Deeply nested expressions
982        assert_eq!(Expression::parse("xqq").unwrap().tree_depth(), 3); // sqrt(sqrt(x))
983        assert_eq!(Expression::parse("12+34+*").unwrap().tree_depth(), 3); // (1+2)*(3+4)
984    }
985
986    #[test]
987    fn test_tree_depth_empty() {
988        // Empty expression has depth 0
989        assert_eq!(Expression::new().tree_depth(), 0);
990    }
991
992    #[test]
993    fn test_tree_depth_malformed() {
994        // Malformed expressions return 0
995        assert_eq!(
996            Expression::from_symbols(&[Symbol::X, Symbol::One]).tree_depth(),
997            0
998        );
999    }
1000
1001    #[test]
1002    fn test_operator_count_atom() {
1003        // Single atom has no operators
1004        assert_eq!(Expression::parse("x").unwrap().operator_count(), 0);
1005        assert_eq!(Expression::parse("1").unwrap().operator_count(), 0);
1006        assert_eq!(Expression::parse("p").unwrap().operator_count(), 0);
1007    }
1008
1009    #[test]
1010    fn test_operator_count_unary() {
1011        // Unary op counts as 1 operator
1012        assert_eq!(Expression::parse("xq").unwrap().operator_count(), 1);
1013        assert_eq!(Expression::parse("xs").unwrap().operator_count(), 1);
1014        assert_eq!(Expression::parse("xn").unwrap().operator_count(), 1);
1015    }
1016
1017    #[test]
1018    fn test_operator_count_binary() {
1019        // Binary op counts as 1 operator
1020        assert_eq!(Expression::parse("12+").unwrap().operator_count(), 1);
1021        assert_eq!(Expression::parse("x2*").unwrap().operator_count(), 1);
1022    }
1023
1024    #[test]
1025    fn test_operator_count_complex() {
1026        // Multiple operators
1027        assert_eq!(Expression::parse("x1+2*").unwrap().operator_count(), 2); // (x+1)*2
1028        assert_eq!(Expression::parse("xq1+").unwrap().operator_count(), 2); // sqrt(x)+1
1029        assert_eq!(Expression::parse("12+34+*").unwrap().operator_count(), 3); // (1+2)*(3+4)
1030    }
1031
1032    #[test]
1033    fn test_operator_count_empty() {
1034        assert_eq!(Expression::new().operator_count(), 0);
1035    }
1036
1037    #[test]
1038    fn test_push_pop_complexity_saturating() {
1039        let mut expr = Expression::new();
1040
1041        // Push should use saturating_add
1042        for _ in 0..1000 {
1043            expr.push(Symbol::X);
1044        }
1045        // Complexity should saturate, not overflow
1046        assert!(expr.complexity() < u32::MAX);
1047
1048        // Pop should use saturating_sub
1049        for _ in 0..1000 {
1050            expr.pop();
1051        }
1052        // Should be back to 0 without underflow
1053        assert_eq!(expr.complexity(), 0);
1054    }
1055
1056    /// Issue 6: to_infix must not silently produce '?' for invalid expressions.
1057    /// Instead, stack underflow in the mid-loop pops is a programming error and
1058    /// should panic with a clear message via expect().
1059    #[test]
1060    #[should_panic(expected = "stack underflow in to_infix")]
1061    fn test_to_infix_panics_on_malformed_expression() {
1062        // An expression with only a binary operator has no operands — stack underflows
1063        // on the first pop inside the loop. from_symbols bypasses parse validation.
1064        let expr = Expression::from_symbols(&[Symbol::Add]);
1065        let _ = expr.to_infix();
1066    }
1067
1068    #[test]
1069    fn test_try_to_infix_returns_err_on_malformed_expression() {
1070        // from_symbols bypasses parse validation, producing a malformed postfix string.
1071        // try_to_infix should return Err(StackUnderflow) rather than panicking.
1072        let expr = Expression::from_symbols(&[Symbol::Add]);
1073        let result = expr.try_to_infix();
1074        assert!(
1075            result.is_err(),
1076            "try_to_infix on malformed expression should return Err, got Ok({:?})",
1077            result.ok()
1078        );
1079    }
1080
1081    #[test]
1082    fn test_try_to_infix_succeeds_on_valid_expression() {
1083        let expr = Expression::parse("32+").unwrap();
1084        let result = expr.try_to_infix();
1085        assert_eq!(result.unwrap(), "3+2");
1086    }
1087}
ries_rs/expr.rs

ries_rs/
expr.rs
