RPN and evaluation tree

First, here is a very good article on "An expression evaluator" with source code. It also gives detailed introduction on RPN (Reverse Polish Notation).
Here is the algorithm to parse in RPN's manner:

for each char of the expression
  decide if the char is part of an operand or of an operator
  if the char is part of an operand,
    append it to the list of operands
  else if the char is part of an operator,
    look up the operator
  match it with supported operators
  compare operator with the preceding operators
  if this operator is prevalent,
    store the operator in a stack
    otherwise, unstack the preceding operator,
               append the preceding operator to the list of operands
               stack the new operator
  end if
  end if
end for

Wiki's article on RPN.

For example: an math expression: 9+8x5-20^3

list 1 (operand)      | list 2 (operator)
9                     |
9                     | +                      
9 8                   | +
9 8                   | + x ( x has precedence over +, so just append x)
9 8 5                 | + x
9 8 5 x               | + - ( x has precedence over -, so remove x, append x to operand list, then  append - to operator list)
9 8 5 x 20            | + -
9 8 5 x 20            | + - ^ (of course, ^ has precedence over -, just append ^ on operator list)
9 8 5 x 20 3          | + - ^
9 8 5 x 20 3 ^        | + - (now start from the tail, remove all elements from operator list and append then to the operand list one by one)
9 8 5 x 20 3 ^ -      | +
9 8 5 x 20 3 ^ - +    |

RPN parsing done!

Calculation starts from the left, push elements onto calc stack.
Whenever you get one operator, do the calculation immediately. push the result onto the stack.

Calculation stack     | comment
9                     |
9 8 5 x               | 8 x 5 = 40
9 40                  |
9 40 20               |
9 40 20 3             |
9 40 20 3 ^           | 20 ^ 3 = 8000
9 40 8000             |
9 40 8000 -           | 40 - 8000 = -7960
9 -7960               |
9 -7960 +             | 9 + (-7960) = -7951
-7951

done! so 9+8x5-20^3 = -7951

Problem UVa 288: Arithmetic Operations With Large Integers

I used BigInt library from shygypsy.com
Just modified the operator ^ to support "repeated squaring".
i.e.,

BigInt BigInt::operator^  (BigInt n){
  
  BigInt result = 1;
  BigInt base = *this;
  while(n > 0) {
    if(n % 2 == 1) {
      result *= base;
    }
    base *= base;
    n /= 2;
  }
    
  return result;
}

// operator precedence
// + - 2+3-4-5+4, use left -> right
// 2*3*4*5, use left->right
// 6^7^8^9, use right->left
bool precedence(int z1, int z2) {
  if(z1 == -10) return true;
  if(z2 == -10) return false;

  if(z1 == z2) return false;
  if(z1 == -5) return true;
  if(z2 == -5) return false;
  return false;
}

char buff[35000];
int main() {
  while(gets(buff) && !feof(stdin)) {
    string b(buff);
    // since op is positive, we use 
    // - negative integer to represent operator, 
    // - positive integer to represent operand
   
    // so we define
    //   **  = ^ = -10
    //   *   = -5
    //   + = -1
    //   - = -2
 
    deque number;
    deque op;
    int pos = 0;
    for(int i = 0; i < b.size(); ++i) {
      if(b[i]>='0' && b[i]<='9') continue;

      // append previous numbers
      number.push_back(BigInt(b.substr(pos, i-pos).c_str()));
      
      int v;
      // power has highest priority
      if(b[i]=='*' && b[i+1] == '*') {
 v = -10;
 ++i;
      } else {
 if(b[i] == '*') v = -5;
 else if(b[i] == '+') v = -1;

 else if(b[i] == '-') v = -2;

 if(!op.empty() && !precedence(v, op.back())) {
   number.push_back(BigInt(op.back()));
   op.pop_back();
 }
      }
 
      op.push_back(v);
      pos = i + 1;
    }
    // append the last number
    number.push_back(BigInt(b.substr(pos).c_str()));
    
    while(!op.empty()) {
      number.push_back(BigInt(op.back()));
      op.pop_back();
    }
    
    /*
    deque tmp(number);
    while(!tmp.empty()){
      cout << tmp.front()<< " ";
      tmp.pop_front();
    }
    printf("\n");*/

    // parse into reverse polish format   
    stack calc;
    while(!number.empty()) {
      BigInt t = number.front();
      number.pop_front();

      // t is an operator
      if( t < 0) {
 BigInt right = calc.top(); calc.pop();
 BigInt left = calc.top();  calc.pop();
 BigInt res;
 if(t == -1) res = left+right;
 else if(t == -2) res = left-right;
 else if(t == -5) res = left*right;
 else res = left^right;

 calc.push(res);
      } else {
 calc.push(t);
      }
    }  
    cout << calc.top()<< endl;
  } 
  return 0;  
}