Click here to Skip to main content
Click here to Skip to main content

Expression evaluator : using RPN

, 5 Nov 2003
Rate this:
Please Sign up or sign in to vote.
An article showing how to evaluate mathematical expressions using reverse polish notation (RPN)

Introduction

This article will demonstrate how to evaluate complex mathematical expressions by converting them from infix notation to postfix notation and evaluating the expression. In the process we will be using STL's stack and string classes. When finished, the program should be able to evaluate expressions such as:

expr = "(12232+(43*43-(250/(3*8))*44)/12-311) * (5==5)"

Background

Most programming languages require that you enter expressions in infix notation that is: operators and operands are intermixed, example: "5*6-3*2*3".

The postfix notation, introduced in 1950 by the Polish logician Jan Lukasiewicz, is a method of representing an expression without using parenthesis and still conserving the precedence rules of the original expression. For example, the previous expression could have been written like: "5 6 * 3 2 * 3 * -"

Explaining the code

Here's is how to convert from an infix notation to postfix notation:

  1. Initialize an empty stack (string stack), prepare input infix expression and clear RPN string
  2. Repeat until we reach end of infix expression
    1. Get token (operand or operator); skip white spaces
    2. If token is:
      1. Left parenthesis: Push it into stack
      2. Right parenthesis: Keep popping from the stack and appending to RPN string until we reach the left parenthesis.
        If stack becomes empty and we didn't reach the left parenthesis then break out with error "Unbalanced parenthesis"
      3. Operator: If stack is empty or operator has a higher precedence than the top of the stack then push operator into stack. Else if operator has lower precedence then we keep popping and appending to RPN string, this is repeated until operator in stack has lower precedence than the current operator.
      4. An operand: we simply append it to RPN string.
    3. When the infix expression is finished, we start popping off the stack and appending to RPN string till stack becomes empty.

Now evaluating a postfix (RPN) expression is even easier:

  1. Initialize stack (integer stack) for storing results, prepare input postfix (or RPN) expression.
  2. Start scanning from left to right till we reach end of RPN expression
  3. Get token, if token is:
    1. An operator:
      1. Get top of stack and store into variable op2; Pop the stack
      2. Get top of stack and store into variable op1; Pop the stack
      3. Do the operation expression in operator on both op1 and op2
      4. Push the result into the stack
    2. An operand: stack its numerical representation into our numerical stack.
  4. At the end of the RPN expression, the stack should only have one value and that should be the result and can be retrieved from the top of the stack.
To use the code:
#include <iostream.h>
#include <string>
#include "ExpressionEvaluator.h"

using std::string;

int main()
{
  long result;
  double resultdbl;
  int err;

  string s;
  
  
  s = "1+2*(1-2-3-4)";
  err = ExpressionEvaluator::calculateLong(s, result);
  if (err != ExpressionEvaluator::eval_ok)
    cout << "Error while evaluating!" << endl;
  else
    cout << "Evaluation of (int):" << s.c_str() << " yielded: " 
      << result << endl;

  s = "1.1/5.5+99-(4.1*(2+1)-5)";
  err = ExpressionEvaluator::calculateDouble(s, resultdbl);
  if (err != ExpressionEvaluator::eval_ok)
    cout << "Error while evaluating!" << endl;
  else
    cout << "Evaluation of (double):" << s.c_str() << " yielded: "
       << resultdbl << endl;

  return 0;
}

Extending the code

This code can be extended to allow you perform other operations, however they must be binary operation (takes two operands). To extended the code simply add a new operator into the "operators" array along with its precedence value. If you introduce a new symbol make sure you add the symbol into the "operators[0]" string too. Precedence is important for generating a proper postfix expression. After adding a new operator, define its behaviour in the "evaluateRPN" function as:

        if (token == "PUT YOUR OPERATOR SYMBOL HERE")
          r = doMyOperation(op1, op2);

Hope you find this code and article useful.

References

History

  • Sunday, November 2, 2003
    • Initial version
  • Monday, November 3, 2003
    • Fixed precedence rule of multiplication
  • Tuesday, November 4, 2003
    • Fixed a bug in isOperator()
    • Added support for negative and positive numbers as: -1 or +1
      (initially they were supported as: 0-1 or 0+1)
    • Added exception handling and foolproof against malformed expression
    • Added >=, <=, != operators

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Elias Bachaalany
Web Developer
United States United States
Elias (aka lallousx86, @0xeb) has always been interested in the making of things and their inner workings.
 
His computer interests include system programming, reverse engineering, writing libraries, tutorials and articles.
 
In his free time, and apart from researching, his favorite reading topics include: dreams, metaphysics, philosophy, psychology and any other human/mystical science.
 
Former employee of Hex-Rays (the creators of IDA Pro), was responsible about many debugger plugins, IDAPython project ownership and what not.
 
Elias currently works at Microsoft as a software security engineer.
 
More articles and blog posts can be found here:
 
- http://lallousx86.wordpress.com/
- http://0xeb.wordpress.com/
- http://www.hexblog.com/?author=3

Comments and Discussions

 
QuestionNOT operator? Pinmembertwinbee4-Jun-08 9:16 
QuestionHow about to offer a unicode version? PinmemberPeter, Chan12-Jul-07 17:38 
AnswerRe: How about to offer a unicode version? Pinmemberlallous16-Jul-07 0:26 
Generalnegative numbers after operators Pinmemberbanjaxx12-Nov-06 5:29 
GeneralRe: negative numbers after operators Pinmemberlallous14-Nov-06 23:42 
GeneralRe: negative numbers after operators Pinmemberbanjaxx16-Nov-06 21:18 
GeneralRe: negative numbers after operators Pinmemberagahowa11-May-10 7:22 
GeneralThanks to the author Pinmemberjewelgal10-Apr-06 16:31 
GeneralRe: Thanks to the author Pinmemberlallous10-Apr-06 21:50 
GeneralRe: Thanks to the author Pinmemberjewelgal11-Apr-06 22:49 
GeneralRe: Thanks to the author Pinmemberlallous11-Apr-06 23:03 
GeneralThanks! (and get rid of std::string) PinmembercccMangus8-Nov-05 11:16 
GeneralRe: Thanks! (and get rid of std::string) Pinmemberlallous11-Nov-05 0:05 
GeneralRe: Thanks! (and get rid of std::string) PinmemberRusty FunkNut13-Aug-06 4:31 
General!= operator Pinmemberarisnova19-Jan-05 8:49 
GeneralRe: != operator Pinmemberlallous19-Jan-05 23:26 
Generalnegation and exponentiation PinsussAnonymous6-Sep-04 19:52 
GeneralRe: negation and exponentiation Pinmemberlallous7-Sep-04 22:04 
Hello there,
 
A quick fix would be to create two operators the "^" and "^-" and two different handlers.
 
You handle the first as postive exponent while the second a negative exponent directly though the input number will be positive since the "-" will be part of the "^-" operator.
 
HTH
Elias
GeneralRe: negation and exponentiation PinmemberDavid Orel11-Sep-04 19:16 
GeneralCool! However, it doesn't take floating point input! PinmembercccMangus14-Aug-04 22:03 
GeneralRe: Cool! However, it doesn't take floating point input! Pinmemberlallous17-Aug-04 22:05 
GeneralRe: Cool! However, it doesn't take floating point input! PinmembercccMangus18-Aug-04 3:57 
QuestionHow about sin PinmemberIsidor18-Jan-04 8:28 
QuestionHow about the OPs that only take one operand? PinmemberCatGor29-Dec-03 0:30 
AnswerRe: How about the OPs that only take one operand? PinmemberStephane Rodriguez.29-Dec-03 1:59 
GeneralRe: How about the OPs that only take one operand? Pinmemberlallous29-Dec-03 4:16 
GeneralRe: How about the OPs that only take one operand? PinmemberCatGor29-Dec-03 14:49 
GeneralRe: How about the OPs that only take one operand? Pinmembernofeel2-Feb-04 19:35 
AnswerRe: How about the OPs that only take one operand? PinmemberCatGor30-Dec-03 16:14 
Generaldexter . PinsussAnonymous6-Dec-03 16:33 
GeneralRe: dexter . Pinmemberlallous8-Dec-03 6:23 
GeneralWell done homework Pinmemberkozlowski6-Nov-03 7:00 
GeneralRe: Well done homework PinmemberTimo_H20-Nov-03 4:32 
GeneralRe: Well done homework Pinmemberkozlowski21-Nov-03 7:20 
GeneralRe: Well done homework PinmemberTimo_H23-Nov-03 21:35 
GeneralRe: Well done homework Pinmemberkozlowski23-Nov-03 22:47 
GeneralRe: Well done homework Pinmemberlallous1-Dec-03 1:09 
Generalchokes on &quot;(((-1 + 1) + 1) + 1)&quot; PinmemberKevinHall3-Nov-03 15:07 
GeneralRe: chokes on "(((-1 + 1) + 1) + 1)" PinmemberJeff Varszegi3-Nov-03 16:58 
GeneralRe: chokes on &quot;(((-1 + 1) + 1) + 1)&quot; Pinmemberlallous3-Nov-03 19:29 
GeneralRe: chokes on &quot;(((-1 + 1) + 1) + 1)&quot; PinmemberKevinHall4-Nov-03 6:19 
GeneralAbout speed Pinmemberlallous4-Nov-03 23:55 
GeneralRe: About speed PinmemberKevinHall5-Nov-03 6:06 
GeneralRe: chokes on &quot;(((-1 + 1) + 1) + 1)&quot; PinmemberKevinHall4-Nov-03 6:33 
GeneralRe: chokes on &quot;(((-1 + 1) + 1) + 1)&quot; PinmemberKevinHall4-Nov-03 6:37 
GeneralRe: chokes on &quot;(((-1 + 1) + 1) + 1)&quot; Pinmemberlallous4-Nov-03 23:11 
GeneralGood job! PinmemberKevinHall3-Nov-03 6:12 
QuestionWhy not using reflection ? PinmemberJonathan de Halleux3-Nov-03 2:17 
AnswerRe: Why not using reflection ? Pinmemberlallous3-Nov-03 3:11 
GeneralRe: Why not using reflection ? PinmemberNormski6-Nov-03 1:17 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.1411023.1 | Last Updated 6 Nov 2003
Article Copyright 2003 by Elias Bachaalany
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid