The postfix notation of fully parethesized arithmetic expressions is an unambigu
ID: 3754596 • Letter: T
Question
The postfix notation of fully parethesized arithmetic expressions is an unambiguous way
of representing expressions without using any parenthesis. If E = (exp1)op(exp2) is a fully
parenthesized expression then the expression p1p2op is the postfix notation of E, where
op is a binary operation and p1 and p2 are the postfix notation of the fully parenthesized sub expressions exp1 and exp2. The postfix notation of any constants or variables are the constants or variables themselves.
For instance, the postfix notation of ((a + 5) * 3) - (b * c)), P((a + 5) * 3) - (b * c)) is
P((a + 5) * 3) - (b * c))
P((a + 5) * 3)P(b * c)-
P((a + 5))3 * P(b * c)-
a 5 + 3 * b c * -
For simplicity, assume that
* variable names and constants appearing in an expression consist of one symbol,
* variables evaluate to the valued they hold and this is given by the function val(.),
* all arithmetic operations occurring in E() are binary operations and
* constants occurring in an expression evaluate to themselves.
Consider the Postfix Notation Evaluation Problem.
Postfix Notation Evaluation -PNE
Instance: An n variable postfix notation expression E(v1, …,vn) and a function
val : {v1, … , vn} R.
Request: Evaluate the expression E(., …,.).
Write an algorithm in pseudocode to solve the PNE, this algorithm reads an expression
one symbol at the time, and the function val(:) as a set of ordered pairs (vi, ki), where
1 i n, vi is a variable name and ki is a real number. Hint: use a queue to hold the
input expression and a stack to help in the evaluation of the expression.
Explanation / Answer
int infixToPostfix(char* exp)
{
int i, k;
// Create a stack of capacity equal to expression size
struct Stack* stack = createStack(strlen(exp));
if(!stack) // See if stack was created successfully
return -1 ;
for (i = 0, k = -1; exp[i]; ++i)
{
// If the scanned character is an operand, add it to output.
if (isOperand(exp[i]))
exp[++k] = exp[i];
// If the scanned character is an ‘(‘, push it to the stack.
else if (exp[i] == '(')
push(stack, exp[i]);
// If the scanned character is an ‘)’, pop and output from the stack
// until an ‘(‘ is encountered.
else if (exp[i] == ')')
{
while (!isEmpty(stack) && peek(stack) != '(')
exp[++k] = pop(stack);
if (!isEmpty(stack) && peek(stack) != '(')
return -1; // invalid expression
else
pop(stack);
}
else // an operator is encountered
{
while (!isEmpty(stack) && Prec(exp[i]) <= Prec(peek(stack)))
exp[++k] = pop(stack);
push(stack, exp[i]);
}
}
// pop all the operators from the stack
while (!isEmpty(stack))
exp[++k] = pop(stack );
exp[++k] = '';
printf( "%sn", exp );
}
so the above code given is a pseducode of infix to postfix conversion
output will be
infix a+b
postfix ab+
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.