Infix expression: The expression is of the form A op B, where an operator is in-between a pair of operands. ex: A+B*C+D
Postfix expression: The expression is of the form A B op, where an operator is followed for a pair of operands. ex: ABC*+D+
Please design an algorithm to transform the input infix expression string into a postfix expression string.
Operators: * / + - ( )
Operands: 'a' ~ 'z'
Hint:
Priority of Operators: ‘*’ and ‘/’ is greater than ‘+’ and ‘- ‘
The order of operands does not change between infix and postfix.
When the input character is operand,just print out.
Use stack to store the visited operators and pop them out at the proper sequence. (When the priority of the operator on top of stack is higher or equal to that of the incoming operator)
'(' has the highest priority, always push to stack. Once pushed, ‘(’ get the lowest priority.
‘)’ has the lowest priority, therefore pop the operators in the stack until you see the matched ‘(’, then eliminate both.
Assume that all input infix expressions are legal. No need to detect illegality.
You may use isalpha() to check whether the input character is operand or not.
For example : isalpha(‘a’) will return true, and isalpha(‘+’) will return false
You can create a stack using the declaration like below:
stack<char> your_stack_name;
and the member function of this stack is:
(1)empty()
(2)size()
(3)push()
(4)pop()
(5)top()
9. You may need to implement a priority function to check a priority of an operator.
Template :
#include <iostream>
#include <stack>
#include <string>
#include <ctype.h>
using namespace std;
int priority (char c){
//TODO
}
void infixtopostfix (string s){
stack<char> your_stack_name;
//TODO
}
int main (){
string s;
cin >> s;
infixtopostfix(s);
}
A legal infix expression string.
A legal postfix expression string. (left-to-right associativity)