Advertisement
Guest User

rpn in C#

a guest
Aug 2nd, 2011
188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 4.72 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Runtime.InteropServices;
  4. using System.Globalization;
  5. using System.Diagnostics;
  6.  
  7. namespace rpn
  8. {
  9.     public class Program
  10.     {
  11.         static void Main(string[] args)
  12.         {
  13.             RPN rpn = new RPN();
  14.  
  15.             Stopwatch stopwatch = Stopwatch.StartNew();
  16.             for (int i = 0; i < 800000; ++i)
  17.                 rpn.Eval("2^3+123.43");
  18.             stopwatch.Stop();
  19.             Console.WriteLine(stopwatch.Elapsed);
  20.             Console.WriteLine("wynik = {0}", rpn.Result);
  21.  
  22.             Console.ReadKey(true);
  23.         }
  24.     }
  25.  
  26.     public class RPN
  27.     {
  28.         [StructLayout(LayoutKind.Explicit)]
  29.         private struct Item
  30.         {
  31.             [FieldOffset(0)]
  32.             public byte operatorType;
  33.  
  34.             [FieldOffset(1)]
  35.             public byte priority;
  36.  
  37.             [FieldOffset(2)]
  38.             public ushort itemType;
  39.            
  40.             [FieldOffset(0)]
  41.             public float number;
  42.         }
  43.  
  44.         public float Result
  45.         {
  46.             get;
  47.             private set;
  48.         }
  49.  
  50.         private Stack<Item> stack;
  51.         private Queue<Item> queue;
  52.  
  53.         public void Eval(string data)
  54.         {
  55.             stack = new Stack<Item>();
  56.             queue = new Queue<Item>();
  57.  
  58.             ToPostfix(data);
  59.             Solve();
  60.         }
  61.  
  62.         private void ToPostfix(string data)
  63.         {
  64.             Item item = new Item();
  65.             for (int i = 0; i < data.Length;)
  66.             {
  67.                 if (char.IsDigit(data[i]))
  68.                 {
  69.                     int pos = i;
  70.                     while (i < data.Length && (char.IsDigit(data[i]) || data[i] == '.')) ++i;
  71.                     //item.number = float.Parse(data.Substring(pos, i - pos), CultureInfo.InvariantCulture);
  72.                     item.number = atof(data.Substring(pos, i - pos));
  73.                     queue.Enqueue(item);
  74.                 }
  75.                 else
  76.                 {
  77.                     item.itemType = 0xFFFF;
  78.                     item.operatorType = (byte)data[i];
  79.                     item.priority = GetOperatorPriority(data[i]);
  80.  
  81.                     while (stack.Count != 0 && item.priority <= stack.Peek().priority)
  82.                         queue.Enqueue(stack.Pop());
  83.  
  84.                     stack.Push(item);
  85.                     ++i;
  86.                 }
  87.             }
  88.  
  89.             while (stack.Count != 0)
  90.                 queue.Enqueue(stack.Pop());
  91.         }
  92.  
  93.         private void Solve()
  94.         {
  95.             while (queue.Count != 0)
  96.             {
  97.                 if (queue.Peek().itemType != 0xFFFF)
  98.                     stack.Push(queue.Dequeue());
  99.                 else
  100.                 {
  101.                     float op2 = stack.Pop().number;
  102.                     float op1 = stack.Peek().number;
  103.  
  104.                     char op = (char)queue.Dequeue().operatorType;
  105.                     Item result = stack.Pop();
  106.                     switch (op)
  107.                     {
  108.                         case '+': result.number = op1 + op2; break;
  109.                         case '-': result.number = op1 - op2; break;
  110.                         case '*': result.number = op1 * op2; break;
  111.                         case '/': result.number = op1 / op2; break;
  112.                         case '^': result.number = (float)Math.Pow((double)op1, (double)op2); break;
  113.                     }
  114.  
  115.                     stack.Push(result);
  116.                 }
  117.             }
  118.  
  119.             Result = stack.Pop().number;
  120.         }
  121.  
  122.         private byte GetOperatorPriority(char op)
  123.         {
  124.             if (op == '+' || op == '-')
  125.                 return 1;
  126.             else if (op == '*' || op == '/')
  127.                 return 2;
  128.             else
  129.                 return 3;
  130.         }
  131.  
  132.         private float atof(string data)
  133.         {
  134.             float sign = 1, value = 0;
  135.             int i = 0;
  136.  
  137.             while (char.IsWhiteSpace(data[i])) i++;
  138.  
  139.             if (data[i] == '-')
  140.             {
  141.                 sign = -1;
  142.                 ++i;
  143.             }
  144.             else if (data[i] == '+')
  145.                 ++i;
  146.  
  147.             while (char.IsDigit(data[i]))
  148.             {
  149.                 value = value * 10 + ((byte)data[i] - '0');
  150.                 ++i;
  151.  
  152.                 if (i >= data.Length) return sign * value;
  153.             }
  154.  
  155.             if (data[i] == '.')
  156.             {
  157.                 float pow10 = 10;
  158.                 ++i;
  159.  
  160.                 while (i < data.Length && char.IsDigit(data[i]))
  161.                 {
  162.                     value += ((byte)data[i] - '0') / pow10;
  163.                     pow10 *= 10;
  164.                     ++i;
  165.                 }
  166.             }
  167.  
  168.             return sign * value;
  169.  
  170.         }
  171.     }
  172. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement