How to parse recursive parentheses correctly?












2














I need to parse a string that contains some parentheses disposed recursively, but i'm having trouble with determining priority of parentheses.
For exemple, I have the string



$truth = "((A^¬B)->C)";


and I need to return what is between the parentheses. I've already done it with the following regex:



preg_match_all("~((.*?))~", $truth, $str);


But the problem is that it returns what is between the first "(" and the first ")", which is




(A^¬B




Instead of this, i need it to 'know' where the parentheses closes correctly, in order to return




(A^¬B)->C




How can I return this respecting the priority order? Thanks!






php regex







share|improve this question
























  • You could just make an exclusion group and match anything but parenthesis with [^()]* instead of .*, but you might probably still run into problems depending on the complexity of the expression you're trying to parse, specially if it's malformed. Regular expressions are handy but they don't apply to every parsing problem.
    – Havenard
    Nov 11 at 1:43












  • Regular expressions are not adequate for parsing a language. Try a parser generator. stackoverflow.com/questions/3720362/…
    – Ralph Ritoch
    Nov 11 at 1:46
















2














I need to parse a string that contains some parentheses disposed recursively, but i'm having trouble with determining priority of parentheses.
For exemple, I have the string



$truth = "((A^¬B)->C)";


and I need to return what is between the parentheses. I've already done it with the following regex:



preg_match_all("~((.*?))~", $truth, $str);


But the problem is that it returns what is between the first "(" and the first ")", which is




(A^¬B




Instead of this, i need it to 'know' where the parentheses closes correctly, in order to return




(A^¬B)->C




How can I return this respecting the priority order? Thanks!






php regex







share|improve this question
























  • You could just make an exclusion group and match anything but parenthesis with [^()]* instead of .*, but you might probably still run into problems depending on the complexity of the expression you're trying to parse, specially if it's malformed. Regular expressions are handy but they don't apply to every parsing problem.
    – Havenard
    Nov 11 at 1:43












  • Regular expressions are not adequate for parsing a language. Try a parser generator. stackoverflow.com/questions/3720362/…
    – Ralph Ritoch
    Nov 11 at 1:46














2












2








2


1





I need to parse a string that contains some parentheses disposed recursively, but i'm having trouble with determining priority of parentheses.
For exemple, I have the string



$truth = "((A^¬B)->C)";


and I need to return what is between the parentheses. I've already done it with the following regex:



preg_match_all("~((.*?))~", $truth, $str);


But the problem is that it returns what is between the first "(" and the first ")", which is




(A^¬B




Instead of this, i need it to 'know' where the parentheses closes correctly, in order to return




(A^¬B)->C




How can I return this respecting the priority order? Thanks!






php regex







share|improve this question















I need to parse a string that contains some parentheses disposed recursively, but i'm having trouble with determining priority of parentheses.
For exemple, I have the string



$truth = "((A^¬B)->C)";


and I need to return what is between the parentheses. I've already done it with the following regex:



preg_match_all("~((.*?))~", $truth, $str);


But the problem is that it returns what is between the first "(" and the first ")", which is




(A^¬B




Instead of this, i need it to 'know' where the parentheses closes correctly, in order to return




(A^¬B)->C




How can I return this respecting the priority order? Thanks!






php regex




php regex






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 11 at 1:37









Nick

22.8k81535




22.8k81535










asked Nov 11 at 1:22









Nicholas Ferreira

284




284












  • You could just make an exclusion group and match anything but parenthesis with [^()]* instead of .*, but you might probably still run into problems depending on the complexity of the expression you're trying to parse, specially if it's malformed. Regular expressions are handy but they don't apply to every parsing problem.
    – Havenard
    Nov 11 at 1:43












  • Regular expressions are not adequate for parsing a language. Try a parser generator. stackoverflow.com/questions/3720362/…
    – Ralph Ritoch
    Nov 11 at 1:46


















  • You could just make an exclusion group and match anything but parenthesis with [^()]* instead of .*, but you might probably still run into problems depending on the complexity of the expression you're trying to parse, specially if it's malformed. Regular expressions are handy but they don't apply to every parsing problem.
    – Havenard
    Nov 11 at 1:43












  • Regular expressions are not adequate for parsing a language. Try a parser generator. stackoverflow.com/questions/3720362/…
    – Ralph Ritoch
    Nov 11 at 1:46
















You could just make an exclusion group and match anything but parenthesis with [^()]* instead of .*, but you might probably still run into problems depending on the complexity of the expression you're trying to parse, specially if it's malformed. Regular expressions are handy but they don't apply to every parsing problem.
– Havenard
Nov 11 at 1:43






You could just make an exclusion group and match anything but parenthesis with [^()]* instead of .*, but you might probably still run into problems depending on the complexity of the expression you're trying to parse, specially if it's malformed. Regular expressions are handy but they don't apply to every parsing problem.
– Havenard
Nov 11 at 1:43














Regular expressions are not adequate for parsing a language. Try a parser generator. stackoverflow.com/questions/3720362/…
– Ralph Ritoch
Nov 11 at 1:46




Regular expressions are not adequate for parsing a language. Try a parser generator. stackoverflow.com/questions/3720362/…
– Ralph Ritoch
Nov 11 at 1:46












2 Answers
2






active

oldest

votes


















3














The main problem you have right now is the ? non-greedy bit. If you change that to just .+ greedy it will match what you want. 



$truth = "((A^¬B)->C)";

preg_match('/(.+)/', $truth, $match);


Try it



Output



(A^¬B)->C


If you want to match the inner pair you can use a recursive subpattern:



$truth = "((A^¬B)->C)";

preg_match('/(([^()]+|(?0)))/', $truth, $match);


Try It online



Output



A^¬B


If you need to go further then that you can make a lexer/parser. I have some examples here:



https://github.com/ArtisticPhoenix/MISC/tree/master/Lexers






share|improve this answer























  • Thanks! It solved my problem. And thanks to the others too, it will be useful. =D
    – Nicholas Ferreira
    Nov 11 at 2:14










  • Sure I just added my output converter to my website, artisticphoenix.com/2018/11/11/output-converter it uses the same parsing idea but can convert var_export and print_r to usable arrays. Something I have to do a lot on here... lol
    – ArtisticPhoenix
    Nov 11 at 2:31










  • @ArtisticPhoenix I was just thinking I was going to have to write the same tool myself! Thanks for sharing...
    – Nick
    Nov 11 at 3:50










  • Sure, My site is still a work in progress. lol. I don't get a lot of time to work on it unfortunately
    – ArtisticPhoenix
    Nov 11 at 3:53



















3














For your sample string, something like this will recursively give you the contents of the parentheses. It works by forcing the parentheses matched to be the outermost pair by using ^[^(]* and [^)]*$ at each end of the regex.



$truth = "((A^¬B)->C)";

while (strpos($truth, '(') !== false) {

    preg_match("~^[^(]*((.*?))[^)]*$~", $truth, $str);

    $truth = $str[1];

    echo "$truthn";

}


Output



(A^¬B)->C 

A^¬B


Note however this will not correctly parse a string such as (A+B)-(C+D). If that could be your scenario, this answer might help.



Demo on 3v4l.org






share|improve this answer























    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "1"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53245032%2fhow-to-parse-recursive-parentheses-correctly%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    3














    The main problem you have right now is the ? non-greedy bit. If you change that to just .+ greedy it will match what you want. 



    $truth = "((A^¬B)->C)";
    
preg_match('/(.+)/', $truth, $match);


    Try it



    Output



    (A^¬B)->C


    If you want to match the inner pair you can use a recursive subpattern:



    $truth = "((A^¬B)->C)";
    
preg_match('/(([^()]+|(?0)))/', $truth, $match);


    Try It online



    Output



    A^¬B


    If you need to go further then that you can make a lexer/parser. I have some examples here:



    https://github.com/ArtisticPhoenix/MISC/tree/master/Lexers






    share|improve this answer























    • Thanks! It solved my problem. And thanks to the others too, it will be useful. =D
      – Nicholas Ferreira
      Nov 11 at 2:14










    • Sure I just added my output converter to my website, artisticphoenix.com/2018/11/11/output-converter it uses the same parsing idea but can convert var_export and print_r to usable arrays. Something I have to do a lot on here... lol
      – ArtisticPhoenix
      Nov 11 at 2:31










    • @ArtisticPhoenix I was just thinking I was going to have to write the same tool myself! Thanks for sharing...
      – Nick
      Nov 11 at 3:50










    • Sure, My site is still a work in progress. lol. I don't get a lot of time to work on it unfortunately
      – ArtisticPhoenix
      Nov 11 at 3:53
















    3














    The main problem you have right now is the ? non-greedy bit. If you change that to just .+ greedy it will match what you want. 



    $truth = "((A^¬B)->C)";
    
preg_match('/(.+)/', $truth, $match);


    Try it



    Output



    (A^¬B)->C


    If you want to match the inner pair you can use a recursive subpattern:



    $truth = "((A^¬B)->C)";
    
preg_match('/(([^()]+|(?0)))/', $truth, $match);


    Try It online



    Output



    A^¬B


    If you need to go further then that you can make a lexer/parser. I have some examples here:



    https://github.com/ArtisticPhoenix/MISC/tree/master/Lexers






    share|improve this answer























    • Thanks! It solved my problem. And thanks to the others too, it will be useful. =D
      – Nicholas Ferreira
      Nov 11 at 2:14










    • Sure I just added my output converter to my website, artisticphoenix.com/2018/11/11/output-converter it uses the same parsing idea but can convert var_export and print_r to usable arrays. Something I have to do a lot on here... lol
      – ArtisticPhoenix
      Nov 11 at 2:31










    • @ArtisticPhoenix I was just thinking I was going to have to write the same tool myself! Thanks for sharing...
      – Nick
      Nov 11 at 3:50










    • Sure, My site is still a work in progress. lol. I don't get a lot of time to work on it unfortunately
      – ArtisticPhoenix
      Nov 11 at 3:53














    3












    3








    3






    The main problem you have right now is the ? non-greedy bit. If you change that to just .+ greedy it will match what you want. 



    $truth = "((A^¬B)->C)";
    
preg_match('/(.+)/', $truth, $match);


    Try it



    Output



    (A^¬B)->C


    If you want to match the inner pair you can use a recursive subpattern:



    $truth = "((A^¬B)->C)";
    
preg_match('/(([^()]+|(?0)))/', $truth, $match);


    Try It online



    Output



    A^¬B


    If you need to go further then that you can make a lexer/parser. I have some examples here:



    https://github.com/ArtisticPhoenix/MISC/tree/master/Lexers






    share|improve this answer














    The main problem you have right now is the ? non-greedy bit. If you change that to just .+ greedy it will match what you want. 



    $truth = "((A^¬B)->C)";
    
preg_match('/(.+)/', $truth, $match);


    Try it



    Output



    (A^¬B)->C


    If you want to match the inner pair you can use a recursive subpattern:



    $truth = "((A^¬B)->C)";
    
preg_match('/(([^()]+|(?0)))/', $truth, $match);


    Try It online



    Output



    A^¬B


    If you need to go further then that you can make a lexer/parser. I have some examples here:



    https://github.com/ArtisticPhoenix/MISC/tree/master/Lexers







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Nov 11 at 2:02

























    answered Nov 11 at 1:56









    ArtisticPhoenix

    15.1k11223




    15.1k11223












    • Thanks! It solved my problem. And thanks to the others too, it will be useful. =D
      – Nicholas Ferreira
      Nov 11 at 2:14










    • Sure I just added my output converter to my website, artisticphoenix.com/2018/11/11/output-converter it uses the same parsing idea but can convert var_export and print_r to usable arrays. Something I have to do a lot on here... lol
      – ArtisticPhoenix
      Nov 11 at 2:31










    • @ArtisticPhoenix I was just thinking I was going to have to write the same tool myself! Thanks for sharing...
      – Nick
      Nov 11 at 3:50










    • Sure, My site is still a work in progress. lol. I don't get a lot of time to work on it unfortunately
      – ArtisticPhoenix
      Nov 11 at 3:53


















    • Thanks! It solved my problem. And thanks to the others too, it will be useful. =D
      – Nicholas Ferreira
      Nov 11 at 2:14










    • Sure I just added my output converter to my website, artisticphoenix.com/2018/11/11/output-converter it uses the same parsing idea but can convert var_export and print_r to usable arrays. Something I have to do a lot on here... lol
      – ArtisticPhoenix
      Nov 11 at 2:31










    • @ArtisticPhoenix I was just thinking I was going to have to write the same tool myself! Thanks for sharing...
      – Nick
      Nov 11 at 3:50










    • Sure, My site is still a work in progress. lol. I don't get a lot of time to work on it unfortunately
      – ArtisticPhoenix
      Nov 11 at 3:53
















    Thanks! It solved my problem. And thanks to the others too, it will be useful. =D
    – Nicholas Ferreira
    Nov 11 at 2:14




    Thanks! It solved my problem. And thanks to the others too, it will be useful. =D
    – Nicholas Ferreira
    Nov 11 at 2:14












    Sure I just added my output converter to my website, artisticphoenix.com/2018/11/11/output-converter it uses the same parsing idea but can convert var_export and print_r to usable arrays. Something I have to do a lot on here... lol
    – ArtisticPhoenix
    Nov 11 at 2:31




    Sure I just added my output converter to my website, artisticphoenix.com/2018/11/11/output-converter it uses the same parsing idea but can convert var_export and print_r to usable arrays. Something I have to do a lot on here... lol
    – ArtisticPhoenix
    Nov 11 at 2:31












    @ArtisticPhoenix I was just thinking I was going to have to write the same tool myself! Thanks for sharing...
    – Nick
    Nov 11 at 3:50




    @ArtisticPhoenix I was just thinking I was going to have to write the same tool myself! Thanks for sharing...
    – Nick
    Nov 11 at 3:50












    Sure, My site is still a work in progress. lol. I don't get a lot of time to work on it unfortunately
    – ArtisticPhoenix
    Nov 11 at 3:53




    Sure, My site is still a work in progress. lol. I don't get a lot of time to work on it unfortunately
    – ArtisticPhoenix
    Nov 11 at 3:53













    3














    For your sample string, something like this will recursively give you the contents of the parentheses. It works by forcing the parentheses matched to be the outermost pair by using ^[^(]* and [^)]*$ at each end of the regex.



    $truth = "((A^¬B)->C)";
    
while (strpos($truth, '(') !== false) {
    
    preg_match("~^[^(]*((.*?))[^)]*$~", $truth, $str);
    
    $truth = $str[1];
    
    echo "$truthn";
    
}


    Output



    (A^¬B)->C 
    
A^¬B


    Note however this will not correctly parse a string such as (A+B)-(C+D). If that could be your scenario, this answer might help.



    Demo on 3v4l.org






    share|improve this answer




























      3














      For your sample string, something like this will recursively give you the contents of the parentheses. It works by forcing the parentheses matched to be the outermost pair by using ^[^(]* and [^)]*$ at each end of the regex.



      $truth = "((A^¬B)->C)";
      
while (strpos($truth, '(') !== false) {
      
    preg_match("~^[^(]*((.*?))[^)]*$~", $truth, $str);
      
    $truth = $str[1];
      
    echo "$truthn";
      
}


      Output



      (A^¬B)->C 
      
A^¬B


      Note however this will not correctly parse a string such as (A+B)-(C+D). If that could be your scenario, this answer might help.



      Demo on 3v4l.org






      share|improve this answer


























        3












        3








        3






        For your sample string, something like this will recursively give you the contents of the parentheses. It works by forcing the parentheses matched to be the outermost pair by using ^[^(]* and [^)]*$ at each end of the regex.



        $truth = "((A^¬B)->C)";
        
while (strpos($truth, '(') !== false) {
        
    preg_match("~^[^(]*((.*?))[^)]*$~", $truth, $str);
        
    $truth = $str[1];
        
    echo "$truthn";
        
}


        Output



        (A^¬B)->C 
        
A^¬B


        Note however this will not correctly parse a string such as (A+B)-(C+D). If that could be your scenario, this answer might help.



        Demo on 3v4l.org






        share|improve this answer














        For your sample string, something like this will recursively give you the contents of the parentheses. It works by forcing the parentheses matched to be the outermost pair by using ^[^(]* and [^)]*$ at each end of the regex.



        $truth = "((A^¬B)->C)";
        
while (strpos($truth, '(') !== false) {
        
    preg_match("~^[^(]*((.*?))[^)]*$~", $truth, $str);
        
    $truth = $str[1];
        
    echo "$truthn";
        
}


        Output



        (A^¬B)->C 
        
A^¬B


        Note however this will not correctly parse a string such as (A+B)-(C+D). If that could be your scenario, this answer might help.



        Demo on 3v4l.org







        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited Nov 11 at 2:12

























        answered Nov 11 at 1:37









        Nick

        22.8k81535




        22.8k81535






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Stack Overflow!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid …



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • Please be sure to answer the question. Provide details and share your research!

            But avoid …



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53245032%2fhow-to-parse-recursive-parentheses-correctly%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            -

            這個網誌中的熱門文章

            Tangent Lines Diagram Along Smooth Curve

            圖片
            7 1 I am trying to replicate a diagram and have a minimal example. I don't know how to add additional tangents between the specified points and preserve smoothness. documentclass{article} usepackage{tikz} usetikzlibrary{calc,intersections} begin{document} begin{tikzpicture} % Axes draw [->, name path=x] (-1,0) -- (11,0) node [right] {$x$}; draw [->] (0,-1) -- (0,6) node [above] {$y$}; % Origin node at (0,0) [below left] {$0$}; % Points coordinate (start) at (1,-0.8); coordinate (c1) at (3,3); coordinate (c2) at (5.5,1.5); coordinate (c3) at (8,4); coordinate (end) at (10.5,-0.8); % show the points foreach n in {start,c1,c2,c3,end} fill [black] (n) circle (2pt) node [below] {}; % join the coordinates draw [thick,name path=curve] (start) to[out=70,in=180] (c1) to[out=0,in=180]
            閱讀完整內容

            Yusuf al-Mu'taman ibn Hud

            圖片
            Main article: Taifa of Zaragoza Al-Mu'taman Ruler of Zaragoza Reign 1081–1085 Predecessor Ahmad al-Muqtadir Successor Al-Mustain II Born Zaragoza Died 1085 Full name Yusuf ibn Ahmad al-Mu'taman ibn Hūd House Banu Hud Yusuf ibn Ahmad al-Mu'taman ibn Hūd (Arabic: المؤتمن بالله يوسف إبن أحمد إبن هود ‎, al-Mutaman bi l-Lah , died c. 1085) was the third king of the Banu Hud dynasty who ruled over the Taifa of Zaragoza from 1081 to 1085. Yusuf al-Mutaman reigned during the height of power of Muslim Zaragoza , following the thriving period of his father Ahmad al-Muqtadir. He continued his father's efforts and created around him a court of intellectuals, living in the beautiful palace of Aljafería, nicknamed as "the palace of joy". Al-Mu'taman was also a scholarly king and a patron of science, philosophy and arts. As an example of a wise king, he knew astrology, philosophy, and especially mathematics, a discipline in which
            閱讀完整內容

            Zucchini

            圖片
            This article is about the vegetable. For other uses, see Zucchini (disambiguation). Zucchini (courgette) A striped and a uniform color zucchini Genus Cucurbita Species Cucurbita pepo Origin 19th century northern Italy The zucchini ( / z uː ˈ k iː n i / , American English) or courgette ( / k ʊər ˈ ʒ ɛ t / , British English) is a summer squash which can reach nearly 1 metre (100 cm; 39 in) in length, but is usually harvested when still immature at about 15 to 25 cm (6 to 10 in). [1] A zucchini is a thin-skinned cultivar of what in Britain and Ireland is referred to as a marrow. [2] [3] In South Africa, a zucchini is known as a baby marrow. Along with certain other squashes and pumpkins, the zucchini belongs to the species Cucurbita pepo . It can be dark or light green. A related hybrid, the golden zucchini, is a deep yellow or orange color. [4] In a culinary context, the zucchini is treated as a vegetable; it is usually cooked and presented as a savory dish o
            閱讀完整內容