java - Getting Logical Subexpressions Using Stack -


i don't have code right now, i'm trying process how i'm going perform algorithm , need ideas.

say have string example:

((a+b)*(c+b)) * (a+c) 

i don't want use regex @ i'm trying figure out how using strictly stack operations. thinking of maybe counting brackets have account double inner-brackets. i'm lost of other ideas.

so string, want derive following:

a+b c+b (a+b)*(c+b) a+c ((a+b)*(c+b)) * (a+c)      // original string 

any ideas?

this solution based on assumption every subexpression surrounded parenthesis (except, maybe, entire expression). it's simplification of shunting-yard algorithm, can parse arbitrary arithmetic expressions:

let's keep stack of tokens (represented strings). stack empty. iterate on string , each character, following:

  1. if it's closing parenthesis, keep popping tokens of stack until opening parenthesis found. concatenate popped tokens (including parenthesis), print result , push stack.
  2. otherwise push token stack.

if number of tokens on stack not one, need print content of stack after algorithm finished (it corresponds case when entire expression not parenthesized).

here example of how works:

let string ((a+b)*(c+d)).

we keep pushing tokens stack until first closing parenthesis encountered. @ point, stack looks [(, (, a, +, b]. keep popping tokens until hit (. after concatenating them, (a+b) , push stack. state of stack [(, (a+b)] now. after that, push tokens until reach next ). stack [(, (a+b), *, (, c, +, d]. after popping, new expression (c+d) , stack becomes [(, (a+b), *, (c+d)]. finally, reach last ) , pop off , entire expression.

note: solution assumes spaces removed string before input processed.

by way, can't solve problem regular expression because language we're dealing in problem not regular.


Comments

Popular posts from this blog

account - Script error login visual studio DefaultLogin_PCore.js -

xcode - CocoaPod Storyboard error: -