Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Converting Infix to Prefix Using Solely Regex
New Posts  All Forums:Forum Nav:

Converting Infix to Prefix Using Solely Regex

post #1 of 2
Thread Starter 
I had to write an infix to prefix converter and figured I'd finally get down and learn how to use regex. I know there are much more popular ways (stacks, binary tree), but I didn't want to look anything up before doing the assignment tongue.gif
What I really like about it though is that the line I've commented is all you need to change the entire operation of the algorithm. It not only populates what the operators to search for are, but it also controls order of operations, so if for some unknown reason you want to deviate from PEMDAS, you go right ahead. It's also only 51 lines long rolleyes.gif

The regex pattern itself looks like hell I know, it took me on and off work for 12 hours to get it tweaked just right, but I'm 99% sure it's bullet proof.
Just figured I'd post it here for posterity's sake, as having searched around I couldn't find anyone who'd done something similar!
Programmed in C#.
Code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace ACSL_4_SR
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Infix to Prefix Converter");
            Console.WriteLine("");
            while (true == true)
            {
                Console.WriteLine("Input infix operation:");
                string infix_input = Console.ReadLine();
                string converted = convertToPrefix(infix_input);
                Console.WriteLine(converted.Replace("(", "").Replace(")", ""));
            }
        }

        static String convertToPrefix(string infix_input)
        {
            char[] operators = new char[4] { '*', '/', '+', '-' };   // Order of operations and operators
            for (int i = 0; i <= operators.Length - 1; i++)
            {
                string pattern = @"([A-Z]+|(?<![A-Z])[\*\-\+]*\((?:[^()]|(?<OPEN>\()|(?<-OPEN>\)))+(?(OPEN)(?!))\))\" + operators[i] + @"([\*\-\+]*[A-Z]|\(.*\))";
                Regex pairs = new Regex(pattern, RegexOptions.IgnoreCase);
                Match m = pairs.Match(infix_input);
                while (m.Success)
                {
                    Group g = m.Groups[1];
                    CaptureCollection cc = g.Captures;
                    Capture c = cc[0];
                    infix_input = infix_input.Insert(c.Index, "(" + operators[i].ToString());
                    infix_input = infix_input.Remove(c.Index + g.Length + 2, 1);
                    g = m.Groups[2];
                    cc = g.Captures;
                    c = cc[0];
                    infix_input = infix_input.Insert(c.Index + g.Length + 1, ")");
                    m = pairs.Match(infix_input);
                }
            }
            return infix_input;
        }
    }
}


Edited by crazyap7 - 4/9/12 at 2:37pm
post #2 of 2
For any future regex work, I recommend: http://www.weitz.de/regex-coach/
smile.gif
Ol' Sandy
(28 items)
 
"Zeus"
(12 items)
 
Elite Preview
(6 items)
 
CPUMotherboardGraphicsRAM
Intel Xeon E3-1230v3 Gigabyte GA-Z97X-UD5H-BK MSI Gaming GTX 980 Kingston 32GB (4x8) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Samsung EVO 1TB Hitachi HDS721010CLA332 Hitachi HDS723020BLA642 
Hard DriveHard DriveHard DriveOptical Drive
Hitachi HDS723020BLA642 Hitachi HUA722010CLA330 WDC WD10EARS-00Z5B1 TSSTcorp CDDVDW SH-S223B 
CoolingCoolingOSMonitor
Phanteks PH-TC14PE with TY-140's Lamptron FCv5 (x2) Windows 8 Pro 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2713HM Topre Realforce 87UB | Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Logitech G700 XTRAC Ripper XXL 
AudioAudioAudioAudio
Beyerdynamic DT-770 Pro 250ohm Schiit Bifrost DAC Schiit Asgard 2 HiVi Swan M50W 2.1 
CPUMotherboardRAMHard Drive
Intel Xeon E5-2620 Super Micro X9SRL-F-B 128GB 1333MHz LSI 9271-8i 
OSPowerCase
VMware ESXi 5.5 SeaSonic SS-400FL2 Fractal Define R3 
CPUMotherboardGraphicsRAM
Intel Core i5-3437U HP EliteBook Folio 9470m  Intel HD Graphics 4000  16GB DDR3 SDRAM 
Hard DriveOS
256GB SSD Windows 10 Insider Preview 
  hide details  
Reply
Ol' Sandy
(28 items)
 
"Zeus"
(12 items)
 
Elite Preview
(6 items)
 
CPUMotherboardGraphicsRAM
Intel Xeon E3-1230v3 Gigabyte GA-Z97X-UD5H-BK MSI Gaming GTX 980 Kingston 32GB (4x8) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Samsung EVO 1TB Hitachi HDS721010CLA332 Hitachi HDS723020BLA642 
Hard DriveHard DriveHard DriveOptical Drive
Hitachi HDS723020BLA642 Hitachi HUA722010CLA330 WDC WD10EARS-00Z5B1 TSSTcorp CDDVDW SH-S223B 
CoolingCoolingOSMonitor
Phanteks PH-TC14PE with TY-140's Lamptron FCv5 (x2) Windows 8 Pro 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2713HM Topre Realforce 87UB | Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Logitech G700 XTRAC Ripper XXL 
AudioAudioAudioAudio
Beyerdynamic DT-770 Pro 250ohm Schiit Bifrost DAC Schiit Asgard 2 HiVi Swan M50W 2.1 
CPUMotherboardRAMHard Drive
Intel Xeon E5-2620 Super Micro X9SRL-F-B 128GB 1333MHz LSI 9271-8i 
OSPowerCase
VMware ESXi 5.5 SeaSonic SS-400FL2 Fractal Define R3 
CPUMotherboardGraphicsRAM
Intel Core i5-3437U HP EliteBook Folio 9470m  Intel HD Graphics 4000  16GB DDR3 SDRAM 
Hard DriveOS
256GB SSD Windows 10 Insider Preview 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Converting Infix to Prefix Using Solely Regex