Assume we have a string of operands and operators, an informal, by hand process is
1. Scan the expression left to right
2. Skip values or variables (operands)
3. When an operator is found, apply the operation to the preceding two operands
4. Replace the two operands and operator with the calculated value (three symbols are replaced with one operand) 5. Continue scanning until only a value remains–the result of the expression
The time complexity is O(n) because each operand is scanned once, and each operation is performed once. A more formal algorithm:
create a new stack
while(input stream is not empty){
token = getNextToken();
if(token instanceof operand){
push(token);
} else if (token instance of operator)
op2 = pop();
op1 = pop();
result = calc(token, op1, op2);
push(result);
}
}
return pop();
