rbn Calcaulator

karkaur

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.

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

Java

C/C++

PHP

C#

HTML

CSS

ASP

Javascript

JQuery

AJAX

XSD

Python

Matlab

R Scripts

Weka

rbn Calcaulator