Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to evaluate an infix expression in just one scan using stacks?

I want to know if there is a way to solve infix expressions in a single pass using 2 stacks? The stacks can be one for operator and the other for operands...

The standard way to solve by shunt-yard algorithm is to convert the infix expression to postfix(reverse polish) and then solve. I don't want to convert the expression first to postfix.

If the expression is like 2*3-(6+5)+8, how to solve?

like image 927
nikoo28 Avatar asked Nov 16 '12 17:11

nikoo28


People also ask

How do you evaluate an infix expression using stack?

To evaluate infix expressions, we need two stacks (operator and operand stack), and to evaluate postfix and prefix expressions, we need only one stack (operand stack).

How many stacks are required for applying evaluation of infix?

Explanation: Two stacks are required for evaluation of infix expression – one for operands and one for operators.

How can stacks be used to evaluate an mathematical expression?

We can evaluate a postfix expression using a stack. Each operator in a postfix string corresponds to the previous two operands . Each time we read an operand we push it onto a stack. When we reach an operator its associated operands (the top two elements on the stack ) are popped out from the stack.


2 Answers

Quite late, but here is the answer.

Take two stacks:

  1. operator stack { for operators and parentheses }.
  2. operand stack.

Algorithm

If character exists to be read:

  1. If character is operand push on the operand stack, if character is (, push on the operator stack.
  2. Else if character is operator
    1. While the top of the operator stack is not of smaller precedence than this character.
    2. Pop operator from operator stack.
    3. Pop two operands (op1 and op2) from operand stack.
    4. Store op1 op op2 on the operand stack back to 2.1.
  3. Else if character is ), do the same as 2.2 - 2.4 till you encounter (.

Else (no more character left to read):

  • Pop operators untill operator stack is not empty.
  • Pop top 2 operands and push op1 op op2 on the operand stack.

return the top value from operand stack.

like image 189
Rohit Avatar answered Oct 02 '22 18:10

Rohit


The method given in the link is really good.

Let me quote the source:

We will use two stacks:  Operand stack: to keep values (numbers)  and  Operator stack: to keep operators (+, -, *, . and ^).     In the following, “process” means, (i) pop operand stack once (value1) (ii) pop operator stack once (operator) (iii) pop operand stack again (value2) (iv) compute value1 operator  value2 (v) push the value obtained in operand stack.             Algorithm:   Until the end of the expression is reached, get one character and perform only one of the steps (a) through (f):  (a) If the character is an operand, push it onto the operand stack.  (b) If the character is an operator, and the operator stack is empty then push it onto the operator stack.  (c) If the character is an operator and the operator stack is not empty, and the character's precedence is greater than the precedence of the stack top of operator stack, then push the character onto the operator stack.  (d) If the character is "(", then push it onto operator stack.  (e) If the character is ")", then "process" as explained above until the corresponding "(" is encountered in operator stack.  At this stage POP the operator stack and ignore "(."  (f) If cases (a), (b), (c), (d) and (e) do not apply, then process as explained above.     When there are no more input characters, keep processing until the operator stack becomes empty.  The values left in the operand stack is the final result of the expression. 

I hope this helps!

like image 30
skrtbhtngr Avatar answered Oct 02 '22 18:10

skrtbhtngr