title: Checking if Boolean Mathematical Formula is in the Proper Form
body: <p>I am creating a program that takes in a boolean expression as a string and converts the infix formula to postfix, while making sure the formula is in a valid form. What I'm having a hard time doing is figuring out a way to check if the inputed formula is valid or not. <strong>NO IMPORTING</strong> is permitted (use built-in python functions/methods), loops and recursion are allowed. If the formula is invalid, return None.</p>
  
  <p>The formula can contain:</p>
  
  <pre><code>variables in 'abcdefghijklmnopqrstuvwxyz'
  operators in '-+*'
  </code></pre>
  
  <p>where - is NOT, + is OR, * is AND</p>
  
  <p>Here are some valid formulas (as Python strings). </p>
  
  <pre><code>"x" 
  "-y" 
  "(x*y)" 
  "((-x+y)*(-y+x))" 
  </code></pre>
  
  <p>Here are some strings that are not formulas. </p>
  
  <pre><code>"X" variable not lower case letter 
  "x*y" missing parentheses 
  "-(x)" extraneous parentheses 
  "(x+(y)*z)" mismatched parentheses
  </code></pre>
  
  <p>Some conversion examples are:</p>
  
  <pre><code>(x+y) -&gt; xy+
  (x*y) -&gt; xy*
  -(x+y) -&gt; xy+-
  -x -&gt; x-
  ((x*y)+(z*x)) -&gt; xy*zx*+
  </code></pre>
  
  <p>A full working program isn't necessary, an algorithm to check if the formula is valid or not is fine.</p>
  
  <p>My current implementation to convert formula from infix to postfix:</p>
  
  <pre><code>def infix_to_postfix(infix_expression):
      precedence  = {}
      precedence["*"] = 2
      precedence["+"] = 2
      precedence["-"] = 2
      precedence["("] = 1
      storage_stack = Stack()
      postfix_list = []
      tokenList = list(infix_expression)
      for token in tokenList:
          if(token not in "-+*()"):
              postfix_list.append(token)
          elif(token == '-'):
              storage_stack.push(token)
          elif(token == '('):
              storage_stack.push(token)
          elif(token == ')'):
              topToken = storage_stack.pop()
              while(topToken != '('):
                  postfix_list.append(topToken)
                  topToken = storage_stack.pop()
          else:
              while(not storage_stack.is_empty() and precedence[storage_stack.peek()] &gt;= precedence[token]):
                  postfix_list.append(storage_stack.pop())
              storage_stack.push(token)
      while(not storage_stack.is_empty()):
          postfix_list.append(storage_stack.pop())
      result = "".join(postfix_list)
      return result
  </code></pre>
  
  <p>I need to find a way to check that the formula is valid <strong>while</strong> changing the positions of the operators and variables. </p>
  
  <p>Edit:</p>
  
  <p>I've come up with part of an algorithm to check if the formula is valid or not:</p>
  
  <pre><code>((a+b)*(c+d))
  F1 = (a+b)
  F2 = (c+d)
  ((a+b)*(c+d)) = (F1 * F2)
  If F1 and F2 are valid, then the whole thing is valid.
  </code></pre>
  
  <p>A formula enclosed with parenthesis is valid if:
  There is ( and ), there is either a + or * in between 2 sub-formulas, and both sub-formulas are valid.</p>
  
  <p>I have this idea of checking, but I have no idea how to implement it. Most likely recursion.</p>