//returns true if stk precedes infix
bool precedes(char stk, char infix) {
//declare an array of operators in precedence order
//considers only 4 operators now
static char prec[] ={'/','*','+','-'};
//check for precedence
for(int i = 0; i <4; i++) {
if(prec[i] == stk)
return true;
if(prec[i] == infix)
return false;
}
}
//convert to postfix
std::string postfix(const std::string &infix) {
int i = 0;
//operator stack
std::stack<char> op_stack;
std::string post_fix;
while(i < infix.length()) {
//if it is a digit add it to postfix
if(isdigit(infix[i]))
post_fix.append(1,infix[i]);
else {
//if operator at the top of stack
//precededs current operator
//pop the operator and add it to
//the post fix string
//repeat this until stack is empty
//or operator at top of stack
//doesn't have higher precedence
while(!op_stack.empty() &&
precedes(op_stack.top(),infix[i])) {
post_fix.append(1, op_stack.top());
op_stack.pop();
}
//push the current operator
op_stack.push(infix[i]);
}
i++;
}
//add everything to the post fix string
while(!op_stack.empty())
{
post_fix.append(1, op_stack.top());
op_stack.pop();
}
return post_fix;
}
Monday, June 7, 2010
Conversion from infix to postfix
Converting a given infix expression to postfix expression is used when numerical expressions are evaluated. Given an expression like A+B*C, the problem is to convert it into expression ABC*+. This is quite a simple problem and involves use of a stack. The idea is to add every digit encountered into postfix string. A stack is used to store operators. Whenever an operator is encountered, if it is of lower precedence than the operator on top of stack then the stack is popped and the operator is added to the postfix string. The popping is continued until the stack is empty. This is a pretty simple problem and the code is given below:
Subscribe to:
Posts (Atom)