计算后续表达式 LectCode之Evaluate Reverse Polish Notation

发布时间:2016-12-9 17:52:01 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"计算后续表达式 LectCode之Evaluate Reverse Polish Notation",主要涉及到计算后续表达式 LectCode之Evaluate Reverse Polish Notation方面的内容,对于计算后续表达式 LectCode之Evaluate Reverse Polish Notation感兴趣的同学可以参考一下。

在记录lectcode这道题目前先说明一下三个相关知识点:前序表达式,中序表达式,后序表达式 前序表达式(Polish Notation 或 Prefix Notation): 前序表达式就是不含括号的算术表达式,而且它是将运算符写在前面,操作数写在后面的表达式,也称为“波兰式”。例如,- 1 + 2 3,它等价于1-(2+3)。         计算一般需要一个栈。         思路如下:         顺序解析字符串数组(输入,如:input=["+","/","*","2",“3”,“-”,“2”,“1”,“*”,“3”,“-”,“4”,“1”],即2*3/(2-1)+3*(4-1)) 从后向前遍历input,遇到数字时,压栈,遇到符号时,计算结果并压栈。 如上计算步骤如下:栈a =>1,4                   a=[1,4] (左边表示栈底) =>  -       a=[3] =>3                       a=[3,3] =>  *                       a=[9] => 1,2                  a=[9,1,2] =>  -                       a=[9,1] => 3,2                  a=[9,1,3,2] =>  *                       a=[9,1,6] =>   /                      a=[9,6] => +                        a=[15] 结束。                     后序表达式(Reverse Polish notation,RPN 或 Postfix notation):     逆波兰记法中,操作符置于操作数的后面。例如表达“三加四”时,写作“3 4 +”,而不是“3 + 4”。如果有多个操作符,操作符置于第二个操作数的后面,所以常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5 +”:先3减去4,再加上5。计算步奏见下文。 中序表达式(Infix notation):     正常表达式,符号在中间,需要借助括号来表示。一般计算机需要将中序表达式转化为前序或者后续进行运算。 如表格: 中序表达式 2*3/(2-1)+3*(4-1) 前序表达式 +/*23-21*3-41 后序表达式 23*21-/341-*+ 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 #include<iostream> #include<vector> #include<stack> #include<string> #include<limits> using namespace std; class Solution { public: int str2int(string str) { // char a[10]; return atoi(str.c_str()); } int getOperator(string str){ if(str=="+") return 0; else if(str=="-") return 1; else if(str=="*") return 2; else if(str=="/") return 3; return -1; } int evalRPN(vector<string> &tokens) { int sum,first_ops,second_ops; stack<int> st_tmp; int op; for(vector<string>::iterator i = tokens.begin();i!=tokens.end();i++){ if(-1!= (op=getOperator(*i))) { if(!st_tmp.empty()){ second_ops=st_tmp.top(); st_tmp.pop(); }else{ return -1; } if(!st_tmp.empty()){ first_ops=st_tmp.top(); st_tmp.pop(); //get second_ops and first_ops switch(op){ case 0: sum=first_ops+second_ops; break; case 1: sum=first_ops-second_ops; break; case 2: sum=first_ops*second_ops; break; case 3: if(0==second_ops) return -1; sum=first_ops/second_ops; break; default: break; } st_tmp.push(sum); }else return -1; } else{ st_tmp.push(str2int(*i)); } } if(!st_tmp.empty()){ sum=st_tmp.top(); st_tmp.pop(); if(st_tmp.empty()) return sum; } return -1; } };

上一篇:linux高级网络配置
下一篇:c语言高级编程指南1 (翻译)

相关文章

相关评论