Skip to content

Latest commit

 

History

History
176 lines (160 loc) · 9.74 KB

notes.org

File metadata and controls

176 lines (160 loc) · 9.74 KB
Raw

ExpressionEvaluator

Introduction

This is the programming assignment for a SDET Test and Automation position.

Problem statement

Write a program to evaluate arithmetic expressions. Input will be text expression strings. Here are some examples: 5 + 14 (8 + 2) * 4 7 + 3 + 9 (6 + 5) * (8 + 2)

Your solution should: · Demonstrate the ability to parse/evaluate arithmetic expressions · Support addition and multiplication and be easily extensible to add other operations later · Be designed and implemented in an object-oriented manner · Not use the “Shunting Yard” algorithm · Contain a testing framework to validate that the solution is functioning as desired · Use whatever tools and languages you are most comfortable with

Clarifications

The main clarification was on why/whether the Shunting Yard (SY) algorithm should not be used.

> The requirement asked that I not use SY. The wiki page indicates SY is an algorithm for parsing mathematical expressions specified in infix notation. It can also > be used to convert an infix notation to a pre/post fix notation. > Sedgewick calls it Dijkstra’s Two-Stack algorithm. Many online examples use SY without mentioning it. The tell-tale sign is probably the single pass that > makes it ideal in implementation and memory resource. > > Anyway, I gather the requirement not to use SY boils down to : > 1) don’t convert to infix/postfix > 2) don’t use 2 stacks. > > Is that your intent?

The intent is that you not copy a readily available solution from the Internet. We want to see an approach that you design and implement. It is okay for you to use available language libraries to help you out. For example, if the language you use has library classes/functions for breaking a string into tokens, you can use the library and not write a tokenizer from scratch.

Additional assumptions

  1. Numbers are base10
  2. The input is like a 4-function calculator. Keys to enter input are 0 to 9 numbers, decimal point, braces and RET. There is no entry for scientific notation, although the results may show up in that notation. There is no entry for very large symbolic numbers such as int.MaxValue Error messages will try to be as helpful as possible.
  3. The operators “+” and “*” are binary operators. The addition of other operations would also be binary, ie “-” and “/”. These can be conditionally compiled with the pragma #define MOREOPERATORS.
  4. Unary operators are excluded for now Leading signs such as +5 and -5 are considered unary operators. Other unary operators are sqrt etc. The code can accomodate unary operators and their precedence but it is less trivial.

Implementation details

Ideas seeded but not fully developed

?Highlights

Preliminary research

Initial research suggests that for industrial strength parsing, it is advisable to use something like Antlr. Since this project is for learning, I found a lightweight C# parser that I thought I could leverage upon. It is called Sprache ( https://github.com/sprache/Sprache ). A separate article “Sprache.Calc: Building Yet Another Expression Evaluator” even gave the implementation for a simple calculator. ( https://www.codeproject.com/Articles/795056/Sprache-Calc-Building-Yet-Another-Expression-Evalu ). Instead of just coping the pattern, I decided to adopt this as a buddy test element. It would then be used to compare its output to that of the expression evaluator I will write.

I tried to devise an algorithm for evaluating an arbitary infix expression and ran into many problems. After clarifying the reasons for being able to reimplement the SY algorithm, I decided that it would be safe to re-implement it from Sedgewick’s 4 line description ( Sedgewicks Algorithms 4th edition, Chapter 1 Section 1.3 on ‘Arithmetic expression evaluation’)

  1. Push operands onto the operand stack.
  2. Push operators onto the operator stack.
  3. Ignore left parentheses.
  4. On encountering a right parenthesis, pop an operator, pop the requisite number of operands, and push onto the operand stack the result of applying that operator to those operands.

There is also a complete java code implementation for reference.

/// /// This is a reimplementation of the “Shunting Yard” algorithm, very clearly described in /// Sedgewicks Algorithms 4th edition, Chapter 1 Section 1.3 on ‘Arithmetic expression evaluation’ : /// … /// An expression consists of parentheses, operators, and operands (numbers). /// Proceeding from left to right and taking these entities one at a time, /// we manipulate the stacks according to four possible cases, as follows: /// 1. Push operands onto the operand stack. /// 2. Push operators onto the operator stack. /// 3. Ignore left parentheses. /// 4. On encountering a right parenthesis, pop an operator, pop the requisite number of operands, and push onto the operand stack the result of applying that operator to those operands. /// After the final right parenthesis has been processed, there is one value on the stack, /// which is the value of the expression. /// … /// Additional helpers are refactored so that the original code logic is not obscured. ///

The functional API

Given that we have one function to implement, it would seeem that the api would be quite simple. In C# parlance, it would be Func<string, Double). While that is minimal, it would be more useful to consider error conditions as well.

Below is an excerpt from Calc.cs that implements this functional interface.

/// <summary> /// The fundamental functional interface is Func<string, Tuple<dynamic?, string?>>, ie /// the input is an expression ( string ) /// and the output is a Tuple. /// The first value of the Tuple is a nullable dynamic, representing the value of the expression, if it evaluates without error. /// The null represents a bad evaluation. /// The second value of the Tuple is a nullable string, representing the error message if any. /// The null represents no errors. /// /// This library provides two implementations of the expression evaluator. /// The KweeCalc is written by yours truly. /// The SimpleCalculator is a test buddy. /// </summary> Calc.cs has 2 implementations, CalcImplKwee and CalcImplSprache. CalcImplKwee is the ? CalcImplSprache is the ?

Deliverable

https://www.codeproject.com/Articles/795056/Sprache-Calc-Building-Yet-Another-Expression-Evalu

Code/Test organization

The code is organized into 3 folders :

  1. lib

This contains the source code for the libraries.

Each library <libraryName> has its accompanying <libraryName>.test that is its companion unit tests.

  1. console

This provides console drivers that wraps the functionality in the libraries for convenient and direct use. It is useful for quick testing.

  1. functionaltest

This is the functional test for

Test implementation

Consoles

3rdParty - Sprache

How to build and run

Shortcomings and improvements

References

Install .Net Core on Windows

Misc

  1. Not very consistent with naming convention and brace placements.
  2. If the idea is simple but it takes a few lines to code, sometimes I try to keep the code in one line. This is very perl-lish in that ???

console\KweeConsole\bin\Debug\netcoreapp3.1\KweeConsole.exe functionaltest\FunctionalSuite1\bin\Debug\netcoreapp3.1/FunctionalSuite1.dll

Test data

(((6 - 12) * (19 * 18) * 4) * ((5 * 16) * (4 * 18) * 19) * (((1 - 13) - 18 + 3) * ((7 + 6) - (8 - 5) + 6) * (8 + 14 + 5) * (12 * 19)) - (18 - 12) + (13 * (7 + (8 + 11) + (17 * 18)) * (10 + 12) * (16 - 10)))

evalutes to exactly 2388888007389546

Manually reduce the expression to ensure this is the case

OK 1. ( ((6 - 12) * (19 * 18) * 4) * ((5 * 16) * (4 * 18) * 19) * (((1 - 13) - 18 + 3) * ((7 + 6) - (8 - 5) + 6) * (8 + 14 + 5) * (12 * 19)) - (18 - 12) + (13 * (7 + (8 + 11) + (17 * 18)) * (10 + 12) * (16 - 10) ) ) == 2388888007389546 Since calc does not have unary -, so keep -8208 as (1-8209) OK ( ((6 - 12) * (19 * 18) * 4) * ((5 * 16) * (4 * 18) * 19) * (((1 - 13) - 18 + 3) * ((7 + 6) - (8 - 5) + 6) * (8 + 14 + 5) * (12 * 19)) - (18 - 12) + (13 * (7 + (8 + 11) + (17 * 18)) * (10 + 12) * (16 - 10) ) ) OK ( (1-8209) * 109440 * (((1 - 13) - 18 + 3) * ((7 + 6) - (8 - 5) + 6) * (8 + 14 + 5) * (12 * 19)) - (18 - 12) + (13 * (7 + (8 + 11) + (17 * 18)) * (10 + 12) * (16 - 10) ) ) OK ( (1-8209) * 109440 * ((1-28) * (16) * (8 + 14 + 5) * (12 * 19)) - (18 - 12) + (13 * (7 + (8 + 11) + (17 * 18)) * (10 + 12) * (16 - 10) ) ) OK ( (1-8209) * 109440 * ( 1-2659393 ) - (18 - 12) + (13 * (7 + (8 + 11) + (17 * 18)) * (10 + 12) * (16 - 10) ) ) OK ( (1-8209) * 109440 * ( 1-2659393 ) - (6) + (13 * ( 332 ) * (10 + 12) * (16 - 10) ) ) OK ( (1-8209) * 109440 * ( 1-2659393 ) - (6) + ( 569712 ) ) OK ( (1-8209) * 109440 * ( 1-2659393 ) + 569706 ) OK ( (8208) * 109440 * 2659392 + 569706 ) OK 2388888006819840 + 569706

((13 * 15 * 19) * (15 * (15 - 7 * (18 + 0)) - (16 * 2) * (3 + 7)) * ((5 - 1) - (2 - 0) * (3 * 18)) * ((12 * 18 - 7) * 16 * ((2 + 6) * (18 * 13) - (16 * 15)) * ((18 - 12) * (3 + 13) * (18 - 2))) + (3 + 6 - 3))

KweeCalc => 6.411500811819418E+18 Foley => 6.41150081181942E+18 This is a rounding error

( (1-8209) * 109440 * ((1-2659393) - (18 - 12) + (13 * (7 + (8 + 11) + (17 * 18)) * (10 + 12) * (16 - 10) ) )

( (1-8209) * 109440 * ((1-2659393) - (18 - 12) + (13 * (7 + (8 + 11) + (17 * 18)) * (10 + 12) * (16 - 10) ) ) Why does this not trigger unbalanced braces?