Your Logic is completely wrong. It’s not about just find the operator but U have to check the precedence of the operator and also once the operator is printed u have to remove that from expression so U have to use Data Structures like Stack
This problem required us to change from ordinary in-fix notation of a basic mathematical expression to a Reverse Polish Notation (RPN) format.
Explanation
The examples provided a clear starting point on what is to be expected if you have no idea what an RPN is. Working through the examples also allows you to image a partial algorithm that might do the job. Most parsing based algorithms and problems usually rely on some form of a FIFO/LIFO structure (i.e. stack/queue) and this problem is no different. The constraints here help alleviate some problems, for example, “variables” are only single letter and there are no numerical digits - also there are only 5 operators and each have different precedence. For starters, take the most simple example (a+(bc)), if you were to scan from left to right you have several issues to deal with:
Parentheses. Obviously you need to keep track of them but how? Since each left bracket ends with a right bracket we can clearly use a stack to help us. For example, in the above we push the first left bracket into the stack, and eventually we encounter the second left bracket, since it doesn’t confine an expression (only a right bracket does assume correct syntax) we also push that to the stack. Then we encounter our first right bracket, so we keep popping elements off the stack until we reach a left bracket which would then conclude the expression. Obviously we need to add other elements such as operators in as well.
Output of operands. If you haven’t realised already, RPN always prints the operands from left to right (with possible operators in between). So effectively we can add an operand to the output if we encounter one. Scanning for one is simple, it’s simply an alphabetic character.
Dealing with operators. Using the stack we are building, we also add in operators. The point is that we can retrieve operations based on what’s between brackets and we can also deal with operator precedence using the stack. How do we accomplish this? Consider the case, ab+c without parentheses, our expected answer would be ab*c+ because multiplication has a higher precedence than addition. So when we scan from left to right, if we encounter an operator we check if its precedence is lower than the one on top of the stack (if theres one), if it’s lower then we immediately pop all of the operators that are higher than the current operator and push them into the output (note if we only look at the top of the stack, if its not an operator we stop, we also stop if the current operator has a higher precedence than the one on the top of the stack at the given time).
Using the example ab+c, we first scan ‘a’ since its an operand we push it to the output. Then we scan '’ since no operators exist on the stack at this time, we simply push it to the stack. Then we scan ‘b’, and push it to the output. Next we have ‘+’, we scan the top of the stack for an operator - we find one and our current operator is lower in precedence than , so we pop '’ off the stack and push it to the output. We check if the new stack has an operator and which is also higher in precedence than addition, we don’t have one (the stack is empty at this stage). We then push ‘+’ into the stack, next we scan the last token, ‘c’ and push that to the output. Once, we finish scanning, we simply “flush” out the stack - so we obtain the required ab*c+.
Combining these three elements correctly we obtain the main core of the algorithm. The “output” can either be a queue or simply a string and we concatenate every time we push into the output. So basically the algorithm is:
1 While there is more input continue to [2] otherwise go to [6]
[2] Scan in the next character
[3] Determine whether it is a bracket, operand, or operator
[4a] If it is an operand, push it to the output
[4b] If it is a left bracket, push onto stack
[4c] If it is a right bracket, keep popping the stack and pushing into the output until a left bracket is encountered
[4d] If it’s an operator - check for precedence if the top of the stack is an operator and it has higher precedence than current operator then pop the stack and push onto output, continue until condition is false. Then push in the current operator into stack.
[5] Go back to 1
[6] Flush the stack into the output
A straightforward C++ implementation of the above algorithm is given below:
> string convert(string input) {
> stack<char> stackOperator;
> queue<char> queueOutput; string
> operators = "+-*/^"; string res; for
> (int i = 0; i < input.size(); i++) {
> if (isalpha(input[i])) {
> queueOutput.push(input[i]); }
> else if (operators.find(input[i]) !=
> string::npos) { while
> (stackOperator.size() > 0 &&
> operators.find(stackOperator.top()) !=
> string::npos
> && (operators.find(input[i]) <=
> operators.find(stackOperator.top())))
> {
> queueOutput.push(stackOperator.top());
> stackOperator.pop(); } stackOperator.push(input[i]); }
> else if (input[i] == '(') {
> stackOperator.push('('); } else
> if (input[i] == ')') { while
> (!stackOperator.empty()) {
> if (stackOperator.top() == '(') {
> stackOperator.pop();
> break;
> }
> queueOutput.push(stackOperator.top());
> stackOperator.pop(); } } }
>
> while (!stackOperator.empty()) {
> queueOutput.push(stackOperator.top());
> stackOperator.pop(); }
>
> while (!queueOutput.empty()) { res
> += queueOutput.front(); queueOutput.pop(); }
>
> return res; }
FOr Further Info
Source Link