Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position. It is also known as postfix notation and is parenthesis-free as long as operator arities are fixed. The description "Polish" refers to the nationality of logician Jan Łukasiewicz, who invented (prefix) Polish notation in the 1920s.In computer science, postfix notation is often used in stack-based and concatenative programming languages. It is also common in dataflow and pipeline-based systems, including Unix pipelines.
The C code for converting an expression into RPN format as required in SPOJ problem 4 is done using one stack to store the members and one integer to denote the opening brackets. The function printRPN takes a string expression and prints the RPN equivalent.
The C code for converting an expression into RPN format as required in SPOJ problem 4 is done using one stack to store the members and one integer to denote the opening brackets. The function printRPN takes a string expression and prints the RPN equivalent.
void printRPN(string s){
stack<string> members;
int opening_brackets = 0;
for(int i=0;i<s.length();i++){
if(s[i]==' ')continue;
else
if(s[i]=='(')opening_brackets++;
else
if(s[i]==')'){
opening_brackets--;
string op1 = members.top();members.pop();
string op2 = members.top();members.pop();
string op3 = members.top();members.pop();
op3.append(op1);
op3.append(op2);
members.push(op3);
}else
members.push(string(1,s[i]));
}
cout << members.top() << endl;
}
