source: trunk/CrypPluginBase/Miscellaneous/BigIntegerHelper.cs @ 1448

Last change on this file since 1448 was 1448, checked in by Sven Rech, 12 years ago

replaced all BigInteger stuff with the new BigInteger class from .net 4.0

But there are still problems with some plugins (Keysearcher, BigInteger Operations...)

File size: 6.6 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using System.Numerics;
6
7namespace Cryptool.PluginBase.Miscellaneous
8{
9    public class BigIntegerHelper
10    {
11        #region internal stuff of expression parser
12
13        private struct TOKEN
14        {
15            public enum Ttype { MULTIPLY, DIVIDE, PLUS, MINUS, POW, BRACKETOPEN, BRACKETCLOSE, INTEGER };
16            public Ttype ttype;
17            public BigInteger integer;
18        }
19
20        private static Stack<TOKEN> scan(string expr)
21        {
22            TOKEN t = new TOKEN();
23            int startIndex = 0;
24            if (expr == "")
25                return new Stack<TOKEN>();
26            switch (expr[0])
27            {
28                case ' ':
29                    return scan(expr.Substring(1));
30                case '(':
31                    t.ttype = TOKEN.Ttype.BRACKETOPEN;
32                    startIndex = 1;
33                    break;
34                case ')':
35                    t.ttype = TOKEN.Ttype.BRACKETCLOSE;
36                    startIndex = 1;
37                    break;
38                case '+':
39                    t.ttype = TOKEN.Ttype.PLUS;
40                    startIndex = 1;
41                    break;
42                case '-':
43                    t.ttype = TOKEN.Ttype.MINUS;
44                    startIndex = 1;
45                    break;
46                case '*':
47                    t.ttype = TOKEN.Ttype.MULTIPLY;
48                    startIndex = 1;
49                    break;
50                case '/':
51                    t.ttype = TOKEN.Ttype.DIVIDE;
52                    startIndex = 1;
53                    break;
54                case '^':
55                    t.ttype = TOKEN.Ttype.POW;
56                    startIndex = 1;
57                    break;
58                case '0':
59                case '1':
60                case '2':
61                case '3':
62                case '4':
63                case '5':
64                case '6':
65                case '7':
66                case '8':
67                case '9':
68                    int length = 1;
69                    for (; length < expr.Length; length++)
70                        if (!(expr[length] >= '0' && expr[length] <= '9'))
71                            break;
72                    t.integer = BigInteger.Parse(expr.Substring(0, length));
73                    t.ttype = TOKEN.Ttype.INTEGER;
74                    startIndex = length;
75                    break;
76                default:
77                    throw new Exception("Expression parsing failed at character " + expr[0]);
78            }
79            Stack<TOKEN> st = scan(expr.Substring(startIndex));
80            st.Push(t);
81            return st;
82        }
83
84        private enum Priority { ALL, POW, MULTDIV, ADDSUB };
85
86        private static BigInteger parse(Stack<TOKEN> stack, Priority priority, bool endbracket)
87        {
88            if (stack.Count == 0)
89                throw new Exception("Expression Parsing Error.");
90            int minus = 1;
91            BigInteger v = 0;
92            TOKEN t = stack.Pop();  //get -, +, integer or bracket
93
94            if (t.ttype == TOKEN.Ttype.MINUS)
95            {
96                minus = -1;
97                t = stack.Pop();    //get integer or bracket
98            }
99            else if (t.ttype == TOKEN.Ttype.PLUS)
100            {
101                minus = 1;
102                t = stack.Pop();    //get integer or bracket
103            }
104
105            if (t.ttype == TOKEN.Ttype.INTEGER)
106            {
107                v = minus * t.integer;
108            }
109            else if (t.ttype == TOKEN.Ttype.BRACKETOPEN)
110            {
111                v = minus * parse(stack, Priority.ALL, true);
112                stack.Pop();    //pop the closing bracket
113            }
114
115            while (stack.Count != 0)
116            {
117                switch (stack.Peek().ttype) //next operator
118                {
119                    case TOKEN.Ttype.PLUS:
120                        if (priority == Priority.MULTDIV || priority == Priority.POW)
121                            return v;
122                        stack.Pop();
123                        v = v + parse(stack, Priority.ADDSUB, endbracket);
124                        break;
125                    case TOKEN.Ttype.MINUS:
126                        if (priority == Priority.MULTDIV || priority == Priority.POW)
127                            return v;
128                        stack.Pop();
129                        v = v - parse(stack, Priority.ADDSUB, endbracket);
130                        break;
131                    case TOKEN.Ttype.MULTIPLY:
132                        if (priority == Priority.POW)
133                            return v;
134                        stack.Pop();
135                        v = v * parse(stack, Priority.MULTDIV, endbracket);
136                        break;
137                    case TOKEN.Ttype.DIVIDE:
138                        if (priority == Priority.POW)
139                            return v;
140                        stack.Pop();
141                        v = v / parse(stack, Priority.MULTDIV, endbracket);
142                        break;
143                    case TOKEN.Ttype.POW:
144                        stack.Pop();
145                        v = BigInteger.Pow(v, (int)parse(stack, Priority.POW, endbracket));
146                        break;
147                    case TOKEN.Ttype.BRACKETCLOSE:
148                        if (endbracket)
149                            return v;
150                        else
151                            throw new Exception("Expression Parsing Error (closing bracket misplaced).");
152                    default:
153                        throw new Exception("Expression Parsing Error.");
154                }
155            }
156            if (endbracket)
157                throw new Exception("Expression Parsing Error (closing bracket missing).");
158
159            return v;
160        }
161
162        #endregion
163
164        /*         
165         * Parses a math expression (example: (2+2)^(17-5) )
166         * and returns a BigInteger based on this expression
167         *
168         * throws an exception when expression is not valid or the Number gets too big
169         */
170        public static BigInteger parseExpression(string expr)
171        {
172            Stack<TOKEN> stack = scan(expr);
173            BigInteger i = parse(stack, Priority.ALL, false);
174            return i;
175        }
176
177        public static BigInteger ModInverse(BigInteger Input1, BigInteger Mod)
178        {
179            throw new NotImplementedException();
180        }
181
182        public static bool isProbablePrime(BigInteger p)
183        {
184            throw new NotImplementedException();
185        }
186    }
187}
Note: See TracBrowser for help on using the repository browser.