-4

I am trying to match brackets using regex in python:

(a (dcsd)) ()

I dont have internet on my desktop at the moment so I cant download new libraries. What is the best way of doing this when regex has no recursive features in python?

More clearly, and for a particular user who cannot read, I do not have internet on my main computer, just some mobile internet that I am using to post this question. I was hoping that someone could suggest a manual algorithm for finding the contents of matched brackets as the only answers I have found using the almighty google use separate libraries.

In that example I would need the result 'a' 'dcsd'

user1212520
  • 501
  • 1
  • 5
  • 15
  • 3
    _i am sorry_,because there is no support of recursion in `re` library..you need `regex` library..BTW, how are you asking question without internet? – rock321987 Jun 26 '16 at 14:21
  • 1
    @rock321987: Good point! – Jan Jun 26 '16 at 14:22
  • If you just want to verify they are *balanced* - without a regular expression: ```s.count('(') == s.count(')')``` – wwii Jun 26 '16 at 14:36
  • 1 - I have no internet on the desktop I need to the run program from. I of course have it on my phone. 2 - Google isnt helping because python does not seem to support recursive regex - hence I am asking for an alternative algorthim that does not involve downloading a new library - something I could not find elsewhere on here, obviously I googled it first – user1212520 Jun 26 '16 at 14:44
  • @user1212520 you can use stack.. – rock321987 Jun 26 '16 at 14:54
  • Please explain what you mean by ```match```: What would be the result of *operating* on your example? – wwii Jun 26 '16 at 14:55
  • @user1212520 i think you can also download the zip file of `regex` library on your mobile and transfer it to your desktop..it will be long process though – rock321987 Jun 26 '16 at 14:55
  • Thanks, I guess I will have to wait until my internet gets connected :( – user1212520 Jun 26 '16 at 15:01

1 Answers1

1

You cannot match brackets using regex, this sentiment is echoed by the comments you have received.

Regular expressions (regex) is a Chomsky Type 3 grammar, whereas finding matching tokens in a string requires a Chomsky Type 2 grammar (or above). Regular expressions have the same descriptive power as a finite automata.

To find matching tokens such as quote symbols, parentheses, braces etc. requires a computational model capable of describing grammars of Chomsky Type 2, namely a pushdown automaton. You might better recognize this as having a "stack".

Filip Allberg
  • 3,941
  • 3
  • 20
  • 37