2

I need algorithms that will check whether given expression is infix, postfix or prefix expression. I have tried a method by checking first or last 2 terms of the string e.g.

+AB if there is an operator in the very first index of string then its a prefix

AB+ if there is an operator in the very last index of string then its a postfix

else it is an infix.

But it doesn't feel appropriate so kindly suggest me a better algorithim.

康桓瑋
  • 33,481
  • 5
  • 40
  • 90
Ahsan
  • 412
  • 5
  • 17
  • This seems perfectly appropriate to me. – Sam Varshavchik Oct 03 '16 at 02:29
  • @SamVarshavchik Except in the case where there is only one term and no operators, but in that case it doesn't matter :-| – user207421 Oct 03 '16 at 02:36
  • @OP You only need to check the first and last terms. Not first two and last two. – user207421 Oct 03 '16 at 03:28
  • @SamVarshavchik what if the expression is **+AB+** or **+A+B**? these expressions are faulty, so how can we check these expressions? According to my **algorithm**, it says the given expression is a prefix, however logically it isn't. – Ahsan Oct 03 '16 at 06:46
  • @EJP what if the expression is **((A+B))** ? now how am I suppose to check it if I am just considering first or last index? I need a different algorithm. Well I know that we can just skip the **()** part or we can say if **(** or **)** is used then it's an infix expression but I think that will be hard coded. – Ahsan Oct 03 '16 at 06:50
  • Logically, it is neither a valid prefix nor a postfix expression. – Sam Varshavchik Oct 03 '16 at 10:40
  • @SamVarshavchik exactly ! So how can we check such expressions? If they are valid or not. – Ahsan Oct 03 '16 at 14:04
  • The only way is by attempting to fully parse them. – Sam Varshavchik Oct 03 '16 at 14:40
  • @SamVarshavchik well obviously I know that, that's why I posted this question. But how am I suppose to do that? – Ahsan Oct 03 '16 at 14:54
  • 1
    There's no trick to it: write the code to parse it. If you don't know how to parse a prefix, postfix, or an infix expression, then that's what you should've asked, instead of some roundabout question, and beat around the bush. Since stack overflow is not a code-writing service, you must try to implement it yourself, first, then ask and show what you've done, and explain what problem you have implementing it. "How to check..." presumes the expression is valid, in which case, just check the 1st or last char. – Sam Varshavchik Oct 03 '16 at 15:41
  • @SamVarshavchik I have already written the code to convert infix to prefix, postfix and vice versa, Now I want to write an algorithm that identify the expression and convert it to other two formats and that's where the problem occurs. As I said in previous comments. What if the expression is false? how to check that? I guess you are not getting my point, so I will just wait for someone else to respond. Well thanks for stopping by. :) – Ahsan Oct 03 '16 at 15:50
  • @AhsanMustafa If the expression is in parentheses it's infix. There are no parentheses in prefix or postfix notation. That's why they exist. If the expression is faulty it is neither prefix, infix, or postfix, which violates the condition implied in your question, but it doesn't matter in the least how you parse it: it will fail. – user207421 Oct 05 '16 at 23:34

2 Answers2

1
  1. If it starts with a valid infix operator it's infix, unless you're going to allow unary operators.
  2. If it ends with a valid postfix operator it's postfix.
  3. Otherwise it is either infix or invalid.

Note that (3) includes the case you mentioned in comments of an expression in parentheses. There are no parentheses in prefix or postfix. That's why they exist. (3) also includes the degenerate case of a single term, e.g. 1, but in that case it doesn't matter how you parse it.

You can only detect an invalid expression by parsing it fully.

If you're going to allow unary operators in infix notation I can only suggest that you try all three parses and stop when you get a success. Very possibly this is the strategy you should follow anyway.

user207421
  • 305,947
  • 44
  • 307
  • 483
0

check the first elements in the string. 1- if the first element is an operator, then it is for sure prefix expression 2- else, check the second element, if it is operator, then it is for sure infix 3- else, it is for sure postfix

Amr Salama
  • 1