Arithmetic evaluation: Difference between revisions

Content added Content deleted
(Rust implementation)
(Formatting had broken something)
Line 5,062: Line 5,062:
=={{header|Rust}}==
=={{header|Rust}}==
<lang rust>//! Simple calculator parser and evaluator
<lang rust>//! Simple calculator parser and evaluator



/// Binary operator
/// Binary operator
Line 5,069: Line 5,070:
Substract,
Substract,
Multiply,
Multiply,
Divide,
Divide
}
}


Line 5,077: Line 5,078:
Value(f64),
Value(f64),
SubNode(Box<Node>),
SubNode(Box<Node>),
Binary(Operator, Box<Node>, Box<Node>),
Binary(Operator, Box<Node>,Box<Node>),
}
}


/// parse a string into a node
/// parse a string into a node
pub fn parse(txt: &str) -> Option<Node> {
pub fn parse(txt :&str) -> Option<Node> {
let chars = txt.chars().filter(|c| *c != ' ').collect();
let chars = txt.chars().filter(|c| *c != ' ').collect();
parse_expression(&chars, 0).map(|(_, n)| n)
parse_expression(&chars, 0).map(|(_,n)| n)
}
}


/// parse an expression into a node, keeping track of the position in the character vector
/// parse an expression into a node, keeping track of the position in the character vector
fn parse_expression(chars: &Vec<char>, pos: usize) -> Option<(usize, Node)> {
fn parse_expression(chars: &Vec<char>, pos: usize) -> Option<(usize,Node)> {
match parse_start(chars, pos) {
match parse_start(chars, pos) {
Some((new_pos, first)) => match parse_operator(chars, new_pos) {
Some((new_pos, first)) => {
Some((new_pos2, op)) => {
match parse_operator(chars, new_pos) {
if let Some((new_pos3, second)) = parse_expression(chars, new_pos2) {
Some((new_pos2,op)) => {
Some((new_pos3, combine(op, first, second)))
if let Some((new_pos3, second)) = parse_expression(chars, new_pos2) {
} else {
Some((new_pos3, combine(op, first, second)))
None
} else {
}
None
⚫
}
⚫
},
None => Some((new_pos,first)),
}
}
None => Some((new_pos, first)),
},
None => None,
None => None,
}
}
Line 5,105: Line 5,109:
fn combine(op: Operator, first: Node, second: Node) -> Node {
fn combine(op: Operator, first: Node, second: Node) -> Node {
match second {
match second {
Node::Binary(op2, v21, v22) => {
Node::Binary(op2,v21,v22) => if precedence(&op)>=precedence(&op2) {
⚫
Node::Binary(op2,Box::new(combine(op,first,*v21)),v22)
if precedence(&op) >= precedence(&op2) {
⚫
} else {
⚫
Node::Binary(op2, Box::new(combine(op, first, *v21)), v22)
⚫
Node::Binary(op,Box::new(first),Box::new(Node::Binary(op2,v21,v22)))
⚫
} else {
⚫
},
⚫
Node::Binary(op, Box::new(first), Box::new(Node::Binary(op2, v21, v22)))
⚫
_ => Node::Binary(op,Box::new(first),Box::new(second)),
⚫
}
⚫
}
⚫
_ => Node::Binary(op, Box::new(first), Box::new(second)),
}
}
}
}
Line 5,118: Line 5,120:
/// a precedence rank for operators
/// a precedence rank for operators
fn precedence(op: &Operator) -> usize {
fn precedence(op: &Operator) -> usize {
match op {
match op{
Operator::Multiply | Operator::Divide => 2,
Operator::Multiply | Operator::Divide => 2,
_ => 1,
_ => 1
}
}
}
}


/// try to parse from the start of an expression (either a parenthesis or a value)
/// try to parse from the start of an expression (either a parenthesis or a value)
fn parse_start(chars: &Vec<char>, pos: usize) -> Option<(usize, Node)> {
fn parse_start(chars: &Vec<char>, pos: usize) -> Option<(usize,Node)> {
match start_parenthesis(chars, pos) {
match start_parenthesis(chars, pos){
Some(new_pos) => {
Some (new_pos) => {
let r = parse_expression(chars, new_pos);
let r = parse_expression(chars, new_pos);
end_parenthesis(chars, r)
end_parenthesis(chars, r)
}
},
None => parse_value(chars, pos),
None => parse_value(chars, pos),
}
}
Line 5,136: Line 5,138:


/// match a starting parentheseis
/// match a starting parentheseis
fn start_parenthesis(chars: &Vec<char>, pos: usize) -> Option<usize> {
fn start_parenthesis(chars: &Vec<char>, pos: usize) -> Option<usize>{
if pos < chars.len() && chars[pos] == '(' {
if pos<chars.len() && chars[pos] == '(' {
Some(pos + 1)
Some(pos+1)
} else {
} else {
None
None
Line 5,145: Line 5,147:


/// match an end parenthesis, if successful will create a sub node contained the wrapped expression
/// match an end parenthesis, if successful will create a sub node contained the wrapped expression
fn end_parenthesis(chars: &Vec<char>, wrapped: Option<(usize, Node)>) -> Option<(usize, Node)> {
fn end_parenthesis(chars: &Vec<char>, wrapped :Option<(usize,Node)>) -> Option<(usize,Node)>{
match wrapped {
match wrapped {
Some((pos, node)) => {
Some((pos, node)) => if pos<chars.len() && chars[pos] == ')' {
if pos < chars.len() && chars[pos] == ')' {
Some((pos+1,Node::SubNode(Box::new(node))))
Some((pos + 1, Node::SubNode(Box::new(node))))
} else {
} else {
None
None
}
},
⚫
}
None => None,
None => None,
}
}
Line 5,159: Line 5,159:


/// parse a value: an decimal with an optional minus sign
/// parse a value: an decimal with an optional minus sign
fn parse_value(chars: &Vec<char>, pos: usize) -> Option<(usize, Node)> {
fn parse_value(chars: &Vec<char>, pos: usize) -> Option<(usize,Node)>{
let mut new_pos = pos;
let mut new_pos = pos;
if new_pos < chars.len() && chars[new_pos] == '-' {
if new_pos<chars.len() && chars[new_pos] == '-' {
new_pos = new_pos + 1;
new_pos = new_pos+1;
}
}
while new_pos < chars.len()
while new_pos<chars.len() && (chars[new_pos]=='.' || (chars[new_pos] >= '0' && chars[new_pos] <= '9')) {
&& (chars[new_pos] == '.' || (chars[new_pos] >= '0' && chars[new_pos] <= '9'))
new_pos = new_pos+1;
⚫
{
new_pos = new_pos + 1;
}
}
if new_pos > pos {
if new_pos>pos {
if let Ok(v) = dbg!(chars[pos..new_pos].iter().collect::<String>()).parse() {
if let Ok(v) = dbg!(chars[pos..new_pos].iter().collect::<String>()).parse() {
Some((new_pos, Node::Value(v)))
Some((new_pos,Node::Value(v)))
} else {
} else {
None
None
Line 5,182: Line 5,180:


/// parse an operator
/// parse an operator
fn parse_operator(chars: &Vec<char>, pos: usize) -> Option<(usize, Operator)> {
fn parse_operator(chars: &Vec<char>, pos: usize) -> Option<(usize,Operator)> {
if pos < chars.len() {
if pos<chars.len() {
let ops_with_char = vec![
let ops_with_char = vec!(('+',Operator::Add),('-',Operator::Substract),('*',Operator::Multiply),('/',Operator::Divide));
('+', Operator::Add),
for (ch,op) in ops_with_char {
('-', Operator::Substract),
('*', Operator::Multiply),
('/', Operator::Divide),
⚫
];
for (ch, op) in ops_with_char {
if chars[pos] == ch {
if chars[pos] == ch {
return Some((pos + 1, op));
return Some((pos+1, op));
}
}
}
}
}
}
None
None
}
}


/// eval a string
/// eval a string
pub fn eval(txt: &str) -> f64 {
pub fn eval(txt :&str) -> f64 {
match parse(txt) {
match parse(txt) {
Some(t) => eval_term(&t),
Some(t) => eval_term(&t),
None => panic!("Cannot parse {}", txt),
None => panic!("Cannot parse {}",txt),
}
}
⚫

}
}


Line 5,213: Line 5,206:
Node::Value(v) => *v,
Node::Value(v) => *v,
Node::SubNode(t) => eval_term(t),
Node::SubNode(t) => eval_term(t),
Node::Binary(Operator::Add, t1, t2) => eval_term(t1) + eval_term(t2),
Node::Binary(Operator::Add,t1,t2) => eval_term(t1) + eval_term(t2),
Node::Binary(Operator::Substract, t1, t2) => eval_term(t1) - eval_term(t2),
Node::Binary(Operator::Substract,t1,t2) => eval_term(t1) - eval_term(t2),
Node::Binary(Operator::Multiply, t1, t2) => eval_term(t1) * eval_term(t2),
Node::Binary(Operator::Multiply,t1,t2) => eval_term(t1) * eval_term(t2),
Node::Binary(Operator::Divide, t1, t2) => eval_term(t1) / eval_term(t2),
Node::Binary(Operator::Divide,t1,t2) => eval_term(t1) / eval_term(t2),
}
}
}
}
Line 5,225: Line 5,218:


#[test]
#[test]
fn test_eval() {
fn test_eval(){
assert_eq!(2.0, eval("2"));
assert_eq!(2.0,eval("2"));
assert_eq!(4.0, eval("2+2"));
assert_eq!(4.0,eval("2+2"));
assert_eq!(11.0 / 4.0, eval("2+3/4"));
assert_eq!(11.0/4.0, eval("2+3/4"));
assert_eq!(2.0, eval("2*3-4"));
assert_eq!(2.0, eval("2*3-4"));
assert_eq!(3.0, eval("1+2*3-4"));
assert_eq!(3.0, eval("1+2*3-4"));
assert_eq!(89.0 / 6.0, eval("2*(3+4)+5/6"));
assert_eq!(89.0/6.0, eval("2*(3+4)+5/6"));
assert_eq!(14.0, eval("2 * (3 -1) + 2 * 5"));
assert_eq!(14.0, eval("2 * (3 -1) + 2 * 5"));
assert_eq!(7000.0, eval("2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10"));
assert_eq!(7000.0, eval("2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10"));
assert_eq!(-9.0 / 4.0, eval("2*-3--4+-.25"));
assert_eq!(-9.0/4.0, eval("2*-3--4+-.25"));
assert_eq!(1.5, eval("1 - 5 * 2 / 20 + 1"));
assert_eq!(1.5, eval("1 - 5 * 2 / 20 + 1"));
assert_eq!(3.5, eval("2 * (3 + ((5) / (7 - 11)))"));
assert_eq!(3.5, eval("2 * (3 + ((5) / (7 - 11)))"));
⚫

}
}
}
}
Retrieved from "https://rosettacode.org/wiki/Arithmetic_evaluation"