ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Simple Expression Tree Evaluator

C#

Goal -- WPM

Ready
Exercise Algorithm Area
1using System;

2using System.Collections.Generic;

3

4public abstract class ExpressionNode

5{

6public abstract double Evaluate();

7}

8

9public class NumberNode : ExpressionNode

10{

11private readonly double value;

12

13public NumberNode(double value)

14{

15this.value = value;

16}

17

18public override double Evaluate()

19{

20return value;

21}

22}

23

24public class OperatorNode : ExpressionNode

25{

26private readonly char op;

27private readonly ExpressionNode left;

28private readonly ExpressionNode right;

29

30public OperatorNode(char op, ExpressionNode left, ExpressionNode right)

31{

32this.op = op;

33this.left = left;

34this.right = right;

35}

36

37public override double Evaluate()

38{

39double leftVal = left.Evaluate();

40double rightVal = right.Evaluate();

41

42switch (op)

43{

44case '+': return leftVal + rightVal;

45case '-': return leftVal - rightVal;

46case '*': return leftVal * rightVal;

47case '/':

48if (rightVal == 0) throw new DivideByZeroException("Division by zero.");

49return leftVal / rightVal;

50default:

51throw new ArgumentException("Unknown operator: " + op);

52}

53}

54}

55

56public class ExpressionParser

57{

58private int position;

59private string expression;

60

61public ExpressionNode Parse(string expression)

62{

63this.expression = expression;

64this.position = 0;

65return ParseExpression();

66}

67

68private ExpressionNode ParseExpression()

69{

70ExpressionNode node = ParseTerm();

71

72while (position < expression.Length && (expression[position] == '+' || expression[position] == '-'))

73{

74char op = expression[position++];

75ExpressionNode right = ParseTerm();

76node = new OperatorNode(op, node, right);

77}

78return node;

79}

80

81private ExpressionNode ParseTerm()

82{

83ExpressionNode node = ParseFactor();

84

85while (position < expression.Length && (expression[position] == '*' || expression[position] == '/'))

86{

87char op = expression[position++];

88ExpressionNode right = ParseFactor();

89node = new OperatorNode(op, node, right);

90}

91return node;

92}

93

94private ExpressionNode ParseFactor()

95{

96SkipWhitespace();

97if (position >= expression.Length) throw new ArgumentException("Unexpected end of expression.");

98

99if (expression[position] == '(')

100{

101position++; // Skip '('

102ExpressionNode node = ParseExpression();

103SkipWhitespace();

104if (position >= expression.Length || expression[position] != ')') throw new ArgumentException("Mismatched parentheses.");

105position++; // Skip ')'

106return node;

107}

108else if (char.IsDigit(expression[position]) || expression[position] == '-') // Handle negative numbers

109{

110int startPos = position;

111if (expression[position] == '-') position++;

112while (position < expression.Length && char.IsDigit(expression[position]))

113{

114position++;

115}

116double value = double.Parse(expression.Substring(startPos, position - startPos));

117return new NumberNode(value);

118}

119else

120{

121throw new ArgumentException("Unexpected character: " + expression[position]);

122}

123}

124

125private void SkipWhitespace()

126{

127while (position < expression.Length && char.IsWhiteSpace(expression[position]))

128{

129position++;

130}

131}

132}
Algorithm description viewbox

Simple Expression Tree Evaluator

Algorithm description:

This C# code provides a basic implementation for parsing and evaluating mathematical expressions. It constructs an expression tree from an infix string and then traverses the tree to compute the result. This is fundamental for building calculators, compilers, and interpreters.

Algorithm explanation:

The code uses a recursive descent parser to build an expression tree. `ParseExpression`, `ParseTerm`, and `ParseFactor` handle addition/subtraction, multiplication/division, and numbers/parentheses respectively, respecting operator precedence. `Evaluate` on the tree nodes performs the actual calculation. Time complexity for parsing and evaluation is O(N) where N is the length of the expression. Space complexity is O(N) for the tree. Edge cases include division by zero, invalid characters, mismatched parentheses, and empty expressions.

Pseudocode:

Define abstract `ExpressionNode` with `Evaluate()`.
Define `NumberNode` inheriting `ExpressionNode` to hold a number.
Define `OperatorNode` inheriting `ExpressionNode` to hold an operator and left/right children.

Class `ExpressionParser`:
  `position`, `expression` fields.

  Function `Parse(expression_string)`:
    Initialize `position` and `expression`.
    Return `ParseExpression()`.

  Function `ParseExpression()`:
    `node = ParseTerm()`.
    While current char is '+' or '-':
      `op = current char`.
      Increment `position`.
      `right = ParseTerm()`.
      `node = new OperatorNode(op, node, right)`.
    Return `node`.

  Function `ParseTerm()`:
    `node = ParseFactor()`.
    While current char is '*' or '/':
      `op = current char`.
      Increment `position`.
      `right = ParseFactor()`.
      `node = new OperatorNode(op, node, right)`.
    Return `node`.

  Function `ParseFactor()`:
    Skip whitespace.
    If current char is '(': 
      Increment `position`.
      `node = ParseExpression()`.
      Skip whitespace.
      If current char is not ')', throw error.
      Increment `position`.
      Return `node`.
    Else if current char is digit or '-':
      Parse number.
      Return `new NumberNode(parsed_number)`.
    Else, throw error.

  Function `SkipWhitespace()`:
    While current char is whitespace, increment `position`.

Function `Evaluate()` on `ExpressionNode` subclasses performs calculation.