[LeetCode]Evaluate Reverse Polish Notation(逆波兰式的计算)

原题链接http://oj.leetcode.com/problems/evaluate-reverse-polish-notation/

题目描述:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +-*/. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

题解:

  所谓逆波兰式,即操作符位于操作数之后的表示法,我们常见的表示“三加四”都是表示成“3+4”,这是一种中缀表达式,换成逆波兰式,就应该表示成3 4 +,因此逆波兰式也称“后缀表达式”,具体的关于逆波兰式中缀表达式波兰式(即前缀表达式),参见*。

  很显然,具体操作符最近的两个数便是与这个操作符对应的操作数,用栈来实现是最直观的,这道题一道比较基础的栈的应用题,详情见代码:

 #include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <iostream>
#include <stack>
using namespace std; int evalRPN(vector<string> &tokens)
{
vector<string>::iterator iter;
stack<int> res;
int a,b;
for (iter=tokens.begin();iter!=tokens.end();iter++)
{
if(*iter=="+" || *iter=="-" || *iter=="*" || *iter=="/")
{
b = res.top();
res.pop();
a = res.top();
res.pop();
if(*iter=="+")
{
res.push(a+b);
}else if(*iter=="-")
{
res.push(a-b);
}else if(*iter=="*")
{
res.push(a*b);
}else if(*iter=="/")
{
res.push(a/b);
}
}
else
{
res.push(atoi((*iter).data()));
}
}
return res.top();
} int main()
{
freopen("in.in","r",stdin);
freopen("out.out","w",stdout); vector<string> tokens; string t;
while(!cin.eof())
{
cin>>t;
tokens.push_back(t);
} printf("%d\n",evalRPN(tokens));
return ;
}
上一篇:第3月30天 UIImage imageWithContentsOfFile卡顿 Can't add self as subview MPMoviePlayerControlle rcrash


下一篇:IReport问题整理