11

What would be a good way to evaluate a string(array, something) that contains a postfix expression(ex: 3 5 +) to check for validity?

Norman Ramsey
  • 198,648
  • 61
  • 360
  • 533

4 Answers4

19

I'm assuming here that what you mean by valid is that executing the code will never underflow the stack and will leave a single value on the stack. If you have a more stringent notion of validity, you'll need a more sophisticated checker.

If you want to check for this kind of validity, it is not necessary to evaluate the string, and you can use a counter, not a stack. The counter tracks the number of values that would be on the stack if you evaluated. To simplify, let's suppose you have only literals, binary operators, and unary operators. This algorithm uses a special decrement operation: if when you decrement, the counter goes below zero, the string is invalid:

  1. Initialize the counter to 0.
  2. When you see a literal, increment the counter.
  3. When you see a binary operator, decrement the counter twice, then increment it.
  4. When you see a unary operator, decrement the counter, then increment it.
  5. At the end of the string, if the counter is 1, and if it never went below 0, the string is valid.
Nico Napoli
  • 1,867
  • 2
  • 13
  • 12
Norman Ramsey
  • 198,648
  • 61
  • 360
  • 533
  • So, according to your instructions, at every alternate literal, the counter should be decremented twice and then incremented? I'm asking because I didn't entirely get them. – Khushman Patel Jul 01 '13 at 03:54
  • 2
    Note that at step 3 and 4 the counter is decremented and then incremented. This is for a reason. You will have to check if the counter went below 0 after every time a counter has been decremented. Otherwise it is possible to validate invalid RPN, e.g.: `[2, +, 2]` would be valid. – Tim Mar 06 '16 at 12:49
  • This would allow for {"12", "5.0", "3","+"} to be valid though. – Mira Welner Oct 10 '21 at 03:06
  • 1
    @ChristopherConnery No, that would leave the counter = 2 at end of execution and answer states check if counter = 1 – pu239 Feb 01 '22 at 16:17
5

A postfix expression is valid if and only if:

1) The first two elements are operands(values), and

2) The last element is an operator, and

3) For every n values there are n-1 operator(s), and

4) In a list of n elements, starting at index i = 0 for i < n-1 (the second to last element), every group of elements consisting of k values( for k > 1 ) is followed by (k-1) operators. When k = 1, the number of operators that follows = k = 1.

Yoshi
  • 51
  • 1
  • 1
  • You don't need that extra 4th condition. If the first 3 conditions are followed for a postfix expression, we can always evaluate that postfix expression. – Kakarot_7 Aug 25 '20 at 07:01
1

Algorithm: maintain a stack and scan the postfix expression from left to right – If the element is a number, push it into the stack – If the element is a operator O, pop twice and get A and B respectively. Calculate BOA and push it back to the stack – When the expression is ended, the number in the stack is the final answer

//For validity If you are left with only one number in Stack its correct expression

//If you are left with more than one number in stack and no operator then its wrong

//If you have one or no number in stack and operators left then its wrong

insanely_sin
  • 986
  • 1
  • 14
  • 22
0

To check if a postfix expression is valid or not:(if input is in char array) 1.Number of operands must equal no. of operators + 1. To check this keep a check variable. check=0. Increment this for every operand and decrement for each operator.If finally its value is 1,then expression is valid.

2.The first 2 elements of the array need to be operands.No postfix expression can have operator as 1st or 2nd element. Check this by if control statement.

Neel Kapadia
  • 1