计算波兰表达式

Question

我在寻找的东西，解释我如何可以计算一个Polish Expression，例如：

，如果我有这个((1+2)*4)+3，以正常的方式是1+2*4+3 = 15，但我需要 写这样：12+4*3+使用stack获得最高的价值，并在堆栈中再次把，看我的代码：https://ideone.com/0bdkkM

我已经看到一个职位，但我不明白我怎么可以让所需要的操作：StackOverflow

Answer 1

这是一个简单的RPN评估器，没有任何错误处理。你只需要一个堆栈来存储操作数，而不是操作符，这使得它很容易实现。

请注意，该版本假设操作数是输入表达式上的单个数字。我这样做是为了简化解析RPN表达式。在现实生活中，你会想要处理多位数的操作数。

std::stack<int> stack; 

const char *expression="12+4*3+"; 

for(char c=*expression; c!=0; c=*expression++) 
{ 
    switch(c) 
    { 
     case '+': 
     { 
      int rhs=stack.top(); stack.pop(); 
      int lhs=stack.top(); stack.pop(); 
      int result=lhs+rhs; 
      stack.push(result); 
      break; 
     } 

     case '-': 
     { 
      int rhs=stack.top(); stack.pop(); 
      int lhs=stack.top(); stack.pop(); 
      int result=lhs-rhs; 
      stack.push(result); 
      break; 
     } 

     case '*': 
     { 
      int rhs=stack.top(); stack.pop(); 
      int lhs=stack.top(); stack.pop(); 
      int result=lhs*rhs; 
      stack.push(result); 
      break; 
     } 

     case '/': 
     { 
      int rhs=stack.top(); stack.pop(); 
      int lhs=stack.top(); stack.pop(); 
      int result=lhs/rhs; 
      stack.push(result); 
      break; 
     } 

     default: 
      int number=(c-'0'); 
      stack.push(number); 
      break; 
    } 
} 

int final_result=stack.top(); 
std::cout << "result is " << final_result << std::endl; 

Answer 2

Reverse Polish成为流行的原因是因为它很好地映射到了堆栈的计算机概念。

当用户输入一个号码时，将其推入堆栈。

当用户输入一个操作符时，从堆栈中弹出2个数字，计算结果并将结果推回堆栈。