I'm trying to figure out from the past several days a way to implement the following logic into a c# program. Using only System.

This is a small console calculator where the input is inserted on a single line in the console. For example the following input / * 65 32 46 2 - 1 1.25 should be translated into a math operation looking like this => ((65 32) * 46) / 2 (1 - 1.25)

Another example would be * 3 2 - 9.5 6.5: this should be calculated in the following order 3 2 * (9.5 - 6.5).

Another example / 5 3 2 equals with => (5 3) / 2

I have to make the function recursive.

I figured out how to make it if all the operations sings are in front of the digits in the input. (I just separate the operator list and inverse it and I get two separate lists: one containing the operation signs and the other containing the numbers). What I'm struggling is to figure out a way to do the operations if there is a math sign in between the numbers (like in the first an the second example).

I don't necessarily need a code for this, maybe an explanation or if somebody could point me to the right direction where I can read about some algorithm / math formula or something that could help me better understand how to implement this.

Thank you in advance.

CodePudding user response：

The normal method of evaluating Polish Notation expressions doesn't require recursion, you use a stack (like Forth or RPN) and evaluate as you go.

An easy way to create a recursive version is to consider the expression language BNF then crafting a recursive descent parser from the grammer.

For example, a possible BNF would be:

expr = op arg arg
op = [ -*/] // cheating; use regex to describe terminal
arg = number | expr
number = [0-9]  // using Regex to describe terminal

So now you would create methods for each element:

double expr() {
    string opStr = op();
    double arg1 = arg();
    double arg2 = arg();

    double ans;
    switch (opStr) {
        case " ":
            ans = arg1 arg2;
            break;
        // case and so on
    }

    return ans;
}

static string operators = " -*/";
string op() {
    if (operators.Contains(peekChar()))
        return nextCharAsStr();
    else
        throw new Exception("Missing operator");
}

double arg() {
    double? num = number();
    if (num.HasValue)
        return num.Value;
    else
        return expr();
}

double? number() {
    string ans = "";
    while (Char.IsDigit(peekChar()))
       ans  = nextCharAsStr();
    if (String.IsNullOrEmpty(ans))
        return null;
    else
        return Double.Parse(ans);
}

NOTE: Whitespace and end of string is left as an exercise to the reader.

You could also use a tokenizer that extracts terminals from the string instead of working directly with characters in the parser terminal methods.

CodePudding user response：

There are different kinds of recursion. The most common (code recursion) is probably what you're asking about, wherein a function (or set of functions) call each other until some sort of exit condition is reached.

For this, I'd go with more of a data recursive approach. This version only supports single-digit operands and binary operators.

(Really bad pseudocode below).

stack<char> operators;
stack<char> operands;

for(var i=input.Length-1; i>=0; --i)
{

    var c = input[i]; 
    if (Char.IsDigit(c)) /// note that this only handles single-digit numbers.
       operands.push(c);
    else 
       operators.push(c);
    
    if (operators.count >= 1 && operands.count >= 2)
    {
       var operator = operators.pop();
       /// handle binary operators
       left = operands.pop();
       right = operands.pop();
       switch(operator) {
          case ' ' : result = left   right; break;
          case '-' : result = left - right; break;
          case '*' : result = left * right; break;
          case '/' : result = left / right; break;
       }
       operands.push(result);
    }        
}

var result = operands.pop();

When that completes, your operands stack should have only one item which is the result of the expression. and operators should be empty. If you have leftover operators, then there weren't enough values in the input. If you have more than one value in operands, there weren't enough operators in the input. If you have zero operands (ie, no result), then there weren't any in the input to start with.

For a real implementation, you'd want to parse the string to get multi-digit operands, handle unary operators, ignore whitespace, etc.

Edit: reversed the loop direction.

CodePudding user response：

So you want something like this:

    static void Main(string[] args)
    {
        Expression expr = Parse("  / *   65 32 46 2 - 1 1.25");
        Console.WriteLine($"f = {expr}");
        // f = ((((65   32) * 46) / 2)   (1 - 1.25))
        Func<double> f = Compile(expr);
        Console.WriteLine($"f = {f()}");
        // f = 2230.75
    }
    public static Func<double> Compile(Expression expr)
    {
        return Expression.Lambda(expr).Compile() as Func<double>;
    }
    public static Expression Parse(string input)
    {
        var tokens = new Tokenizer(input);
        return Parse(tokens);
    }

There are two parts this.

1. First split the input into substrings using the white space. Use input.Split() for that. Then, scan the parts from right to left (from last to first) and extract tokens. A token is a substring that might represent a number or an operation (or a variable if you extend the code below). This is the job of Tokenizer class, the implements IEnumerable<TokenInfo> to act as a collection. A TokenInfo is a data type that describes each token, and it contains the following:

   • An identifying tag of enum Token.Number, Token.Operator or Token.End

   • The string text identifying the operator (when applicable)

   • The double value representing a number (when applicable)

       public enum Token
       {
           Unknown,
           Number,
           Operator,
           End
       }
     
       public struct TokenInfo
       {
           public TokenInfo(Token token)
           {
               Token=token;
               Text = string.Empty;
               Value = 0;
           }
     
           public TokenInfo(string op) : this(Token.Operator)
           {
               Text = op;
           }
           public TokenInfo(double value) : this(Token.Number)
           {
               Value = value;
           }
           public TokenInfo(Token token, string text) : this(token)
           {
               Text = text;
           }
           public Token Token { get; }
           public string Text { get; }
           public double Value { get; }
       }
     
       public class Tokenizer : IEnumerable<TokenInfo>
       {
           readonly string[] operators = new[] { " ", "-", "*", "/" };
           readonly List<TokenInfo> tokens;
           public Tokenizer(string input)
           {
               tokens = new List<TokenInfo>();
               string[] parts = input.Split(' ');
               for (int i = parts.Length - 1; i >= 0; i--)
               {
                   if (operators.Contains(parts[i]))
                   {
                       tokens.Add(new TokenInfo(parts[i]));
                   }
                   else if (double.TryParse(parts[i], out var x))
                   {
                       tokens.Add(new TokenInfo(x));
                   }
                   else
                   {
                       tokens.Add(new TokenInfo(Token.Unknown, parts[i]));
                   }
               }
               tokens.Add(new TokenInfo(Token.End));
           }
     
           public IEnumerator<TokenInfo> GetEnumerator()
           {
               return tokens.GetEnumerator();
           }
     
           System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
           {
               return GetEnumerator();
           }
       }
     

2. Parse the list of tokens and built the expression tree. Keep a Stack<Expression> and assume the top expression is always the result of the previous operation. Also what gets returned in the end is the top of the stack, if it is only one expression tall. Otherwise, there is an imbalance in the operators and/or the values.

   Do the following for each Token type

   • Token.Number parse the value of the number using double.TryParse() and add a ConstantExpression on the stack

   • Token.Operator pull two values from the top of the stack and add an appropriate BinaryEpression to the stack. Possible options are Expression.Add(), Expression.Subtract(), Expression.Multiply(), and Expression.Divide()

   • Token.End return the last expression of the top of the stack.

      public static Expression Parse(IEnumerable<TokenInfo> tokens)
      {
          Stack<Expression> stack = new Stack<Expression>();
          foreach (var item in tokens)
          {
              switch (item.Token)
              {
                  case Token.Number:
                      {
                          var expr = Expression.Constant(item.Value, typeof(double));
                          stack.Push(expr);
                      }
                      break;
                  case Token.Operator:
                      {
                          var arg1 = stack.Pop();
                          var arg2 = stack.Pop();
                          switch (item.Text)
                          {
                              case " ":
                                  stack.Push(Expression.Add(arg1, arg2));
                                  break;
                              case "-":
                                  stack.Push(Expression.Subtract(arg1, arg2));
                                  break;
                              case "*":
                                  stack.Push(Expression.Multiply(arg1, arg2));
                                  break;
                              case "/":
                                  stack.Push(Expression.Divide(arg1, arg2));
                                  break;
                              default:
                                  throw new NotSupportedException($"Invalid operator {item.Text}.");
                          }
                      }
                      break;
                  case Token.End:
                      {
                          if (stack.Count != 1)
                          {
                              throw new InvalidOperationException("Imbalanced expression tree.");
                          }
                          return stack.Pop();
                      }
              }
          }
          throw new ArgumentException($"Invalid expression.", nameof(tokens));
      }
     

3. Optionally the Expression can be compiled into a function, using the Compile() function above. This code assumes there are no ParameterExpression nodes in the expression tree which would need to be accounted for as arguments to the compiled function.

   The addition of variables in the expression and the subsequent compilation into unary or binary functions is pretty straightforward. Add a Token for a variable, produce an appropriate TokenInfo when a string that is not an operator is encountered in the tokenizer and then add ParameterExpression objects to the stack, just like numeric values are added. The compilation parts need references to these parameters from the tree so a custom ExpressionVistor would be needed to extract those nodes.