rbn Calcaulator

Infix to postfix.
The problem remains: given an infix expression, how do we convert it to postfix notation. For example, the infix expression (2+3)*(4+5) in postfix notation is 23+45+* and the infix expression 2+3*4+5 in postfix notation is 234*+5+. Also, since our four operators are left associative, 2 + 3 + 4 translates to 23+4+ and not 234++. While both of these postfix expressions evaluate to 7, the first is interpreted as (2+3)+4 (correct) and the second as 2 + (3+4) (incorrect associativity). By ignoring the associativity of operators, you could run into trouble with subtraction and division. The infix expression 2-3+4 is evaluated as (2-3)+4 = (-1)+4 = 3. The correct postfix is 23-4+ and not 234+- (which is equivalent to 2- (3+4) and evaluates to -5).

Once again, we can use a stack to facilitate the conversion of infix to postfix. This time, however, we will use a stack of characters to store the operators in the expression. To convert correctly formed infix expressions to postfix we will use the following algorithm.

While characters remain in the infix string

• read the next character in the infix string
  
• if the character is an operand, output the character to the postfix expression
  
• if the character is an operator @ :
  while an operator of greater or equal priority is on the stack
  pop the stack and append the operator to the postfix
  push @
  
• if the character is a left parenthesis (
  push the parenthesis onto the stack
  
• if the character is a right parenthesis )
  while the top of the stack is not a matching left parenthesis (
  pop the stack and append the operator to postfix
  pop the stack and discard the returned left parenthesis
  Pop any remaining items on the stack and append to postfix.
  

Let's look at a few examples.

Code:

Input            Stack         Postfix
2*3 + 4*5         empty
*3+4*5         empty         2
3+4*5            *         2
+4*5            *         23
4*5            +         23*
*5            +         23*4
5            *+         23*4
            *+         23*45
            +         23*45*
            empty         23*45*+

Input            Stack         Postfix
2-3+4-5*6         empty               
-3+4-5*6         empty         2      
3+4-5*6         -         2      
+4-5*6            -         23      
4-5*6            +         23-      
-5*6            +         23-4      
5*6            -         23-4+
*6            -         23-4+5
6            *-         23-4+5
            *-         23-4+56
            -         23-4+56*
            empty         23-4+56*-
            

Input            Stack         Postfix
(2-3+4)*(5+6*7)      empty   
2-3+4)*(5+6*7)      (         
-3+4)*(5+6*7)         (         2
3+4)*(5+6*7)         (-         2
+4)*(5+6*7)         (-         23
4)*(5+6*7)         (+         23-
)*(5+6*7)         (+         23-4
*(5+6*7)         empty         23-4+
(5+6*7)         *         23-4+
5+6*7)            (*         23-4+
+6*7)            (*         23-4+5
6*7)            +(*         23-4+5
*7)            +(*         23-4+56
7)            *+(*         23-4+56
)            *+(*         23-4+567
            *         23-4+567*+
            empty         23-4+567*+*




the best for you

Attachments

rbn.cpp

(4.97 KiB) Downloaded 1446 times