Changeset 611 for trunk/CrypPluginBase


Ignore:
Timestamp:
Sep 30, 2009, 1:28:47 PM (12 years ago)
Author:
Sven Rech
Message:

BigInteger expression parser started

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPluginBase/Miscellaneous/BigInteger.cs

    r610 r611  
    133133
    134134using System;
     135using System.Collections;
     136using System.Collections.Generic;
    135137
    136138namespace Cryptool.PluginBase.Miscellaneous
     
    33823384
    33833385        #endregion
     3386
     3387        private struct TOKEN
     3388        {
     3389            public enum Ttype { MULTIPLY, DIVIDE, PLUS, MINUS, POW, BRACKETOPEN, BRACKETCLOSE, INTEGER };
     3390            public Ttype ttype;
     3391            public BigInteger integer;
     3392        }
     3393
     3394        private static Stack<TOKEN> scan(string expr)
     3395        {
     3396            TOKEN t = new TOKEN();
     3397            int startIndex = 0;
     3398            if (expr == "")
     3399                return new Stack<TOKEN>();
     3400            switch (expr[0])
     3401            {
     3402                case ' ':
     3403                    return scan(expr.Substring(1));
     3404                case '(':                   
     3405                    t.ttype = TOKEN.Ttype.BRACKETOPEN;
     3406                    startIndex = 1;
     3407                    break;
     3408                case ')':                   
     3409                    t.ttype = TOKEN.Ttype.BRACKETCLOSE;
     3410                    startIndex = 1;
     3411                    break;
     3412                case '+':
     3413                    t.ttype = TOKEN.Ttype.PLUS;
     3414                    startIndex = 1;
     3415                    break;
     3416                case '-':
     3417                    t.ttype = TOKEN.Ttype.MINUS;
     3418                    startIndex = 1;
     3419                    break;
     3420                case '*':
     3421                    t.ttype = TOKEN.Ttype.MULTIPLY;
     3422                    startIndex = 1;
     3423                    break;
     3424                case '/':
     3425                    t.ttype = TOKEN.Ttype.DIVIDE;
     3426                    startIndex = 1;
     3427                    break;
     3428                case '^':
     3429                    t.ttype = TOKEN.Ttype.POW;
     3430                    startIndex = 1;
     3431                    break;
     3432                case '0':
     3433                case '1':
     3434                case '2':
     3435                case '3':
     3436                case '4':
     3437                case '5':
     3438                case '6':
     3439                case '7':
     3440                case '8':
     3441                case '9':
     3442                    int length = 1;
     3443                    for (; length < expr.Length; length++)
     3444                        if (!(expr[length] >= '0' && expr[length] <= '9'))
     3445                            break;
     3446                    t.integer = new BigInteger(expr.Substring(0, length), 10);
     3447                    t.ttype = TOKEN.Ttype.INTEGER;
     3448                    startIndex = length;
     3449                    break;
     3450                default:
     3451                    throw new Exception("Expression parsing failed at character " + expr[0]);                   
     3452            }
     3453            Stack<TOKEN> st = scan(expr.Substring(startIndex));
     3454            st.Push(t);
     3455            return st;           
     3456        }
     3457
     3458        private enum Priority { ALL /*whole string*/, ENDBRACKET, POW, MULTDIV, ADDSUB };
     3459
     3460        private static BigInteger parse(Stack<TOKEN> stack, Priority priority)
     3461        {
     3462            if (stack.Count == 0)
     3463                throw new Exception("Expression Parsing Error");
     3464            int minus = 1;
     3465            BigInteger v = 0;
     3466            TOKEN t = stack.Pop();  //get -, + or Integer
     3467
     3468            if (t.ttype == TOKEN.Ttype.MINUS)
     3469            {
     3470                minus = -1;
     3471                t = stack.Pop();    //get integer
     3472            }
     3473            else if (t.ttype == TOKEN.Ttype.PLUS)
     3474            {
     3475                minus = 1;
     3476                t = stack.Pop();    //get integer
     3477            }
     3478
     3479            if (t.ttype == TOKEN.Ttype.INTEGER)
     3480            {
     3481
     3482                v = minus * t.integer;
     3483                if (stack.Count == 0)
     3484                    if (priority == Priority.ENDBRACKET)
     3485                        throw new Exception("Expression Parsing Error (bracket close missing)");
     3486                    else
     3487                        return v;
     3488                t = stack.Pop();    //get operator
     3489                switch (t.ttype)
     3490                {
     3491                    case TOKEN.Ttype.PLUS:
     3492                        if (priority == Priority.ADDSUB)
     3493                        {
     3494                            stack.Push(t);
     3495                            return v;
     3496                        }
     3497                        v = v + parse(stack, Priority.ADDSUB);
     3498                        break;
     3499                    case TOKEN.Ttype.MINUS:
     3500                        if (priority == Priority.ADDSUB)
     3501                        {
     3502                            stack.Push(t);
     3503                            return v;
     3504                        }
     3505                        v = v - parse(stack, Priority.ADDSUB);
     3506                        break;
     3507                    case TOKEN.Ttype.MULTIPLY:
     3508                        if (priority == Priority.MULTDIV)
     3509                        {
     3510                            stack.Push(t);
     3511                            return v;
     3512                        }
     3513                        v = v * parse(stack, Priority.MULTDIV);
     3514                        break;
     3515                    case TOKEN.Ttype.DIVIDE:
     3516                        if (priority == Priority.MULTDIV)
     3517                        {
     3518                            stack.Push(t);
     3519                            return v;
     3520                        }
     3521                        v = v / parse(stack, Priority.MULTDIV);
     3522                        break;
     3523                    case TOKEN.Ttype.POW:
     3524                        if (priority == Priority.POW)
     3525                        {
     3526                            stack.Push(t);
     3527                            return v;
     3528                        }
     3529                        v = v / parse(stack, Priority.POW);
     3530                        break;
     3531                }
     3532            }
     3533            else if (t.ttype == TOKEN.Ttype.BRACKETOPEN)
     3534            {
     3535                v = minus * parse(stack, Priority.ENDBRACKET);
     3536            }
     3537
     3538            return v;
     3539        }
     3540
     3541        public static BigInteger parseExpression(string expr) {
     3542            Stack<TOKEN> stack = scan(expr);
     3543            return parse(stack, Priority.ALL);
     3544            return null;
     3545        }
    33843546    }
    33853547}
Note: See TracChangeset for help on using the changeset viewer.