Evaluate Reverse Polish Notation

An expresion in Reverse Polish Notation (RPN) is written such that each binary operator is placed after its operands. For example, the RPN 2 3 + will produce the sum of 2 and 3, namely 5.

Given a RPN expression consisting operands and binary operators + - * /, evaluate it.

For example,

["4", "1", "+", "2", "*"] = (4 + 1) * 2 = 10

["5", "8", "4", "/", "+"] = 5 + (8 / 4) = 7

Solution: use a stack. Keep pushing numbers into the stack, until you meet an operator. Pop two numbers from the stack, apply the operation, and push the result to stack. Using C language, you have to implement the stack yourself.

C语言: ReversePolish

01 #include<stdio.h>
02 #define STACK_SIZE 1000
03 
04 int stack[STACK_SIZE];
05 int stack_top=0;
06 void push(int value)
07 {
08      if(stack_top==STACK_SIZE) {
09          printf("stack overflow!");
10      }        
11      stack[stack_top++]=value;
12 }
13 
14 int pop()
15 {
16     if(stack_top==0) {
17         printf("stack is empty!");
18     }
19     return stack[--stack_top];  
20 }
21 
22 int isOperator(char *str)
23 {
24      char *p=str;
25      if(*p=='+' || *p=='-' || *p=='*' || *p=='/')
26      {
27          return 1;
28      }
29      else
30          return 0;
31 }
32 int main(int argc, char *argv[])
33 {
34     int i;  
35     for( i=1;i<argc;i++)
36     {
37         if(!isOperator(argv[i]))
38         {
39             push(atoi(argv[i]));
40         }
41         else
42         {
43             int op2=pop();
44             int op1=pop();
45             int value;
46             if(argv[i][0]=='+')
47             {
48                 value=op1+op2;
49             }
50             else if(argv[i][0]=='-')
51             {
52                  value=op1-op2;
53             }
54           
55             else if(argv[i][0]=='*')
56             {
57                  value=op1*op2;
58              }
59           
60              else if(argv[i][0]=='/')
61              {
62                  value=op1/op2;
63              }
64             push(value);          
65         }      
66     }
67     int result=pop();
68     printf("%d\n",result);
69   
70     printf("Press any key to continue...");
71     getch();
72     return 0;
73 }