C++代码实现逆波兰式

100行以内C++代码实现逆波兰式

逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)。

算术表达式转逆波兰式例子:

逆波兰式整体的算法流程图如下:

下面给出我基于C++ 语言对逆波兰式算法的实现代码,值得注意的是:

1、算法中对操作数,仅支持一个字符的字母或数字的操作数,如:x,y,j,k,3,7等;如果要支持多个字符的操作数,如:var1,3.14等。需要读者自己扩展对算术表达式操作数的分词部分的代码。

2、为了为了增加转换后的逆波兰表达式的可读性,我在每个操作数和操作符输出时后面追加了一个空格。

代码如下:

/// file: ReversePolishNotation.h
#include <string>
#include <stack>

class ReversePolishNotation {
private:
 std::string _expr;
 unsigned _idx;
 std::stack<std::string> _stk;
public:
 ReversePolishNotation(const std::string &expr);

 std::string nextWord();

 std::string operator()();

 static int getOpPriority(const std::string &word);

 bool isWord(const std::string &word);

 bool isOperator(const std::string &word);
};
/// file: ReversePolishNotation.cpp
#include <iostream>
#include <cassert>
#include "ReversePolishNotation.h"
#include <cctype>
#include <sstream>

using std::cout;
using std::endl;

ReversePolishNotation::ReversePolishNotation(
 const std::string &expr) : _idx(0), _expr(expr) {}

std::string ReversePolishNotation::nextWord() {
 if (_idx >= _expr.length()) {
 return "";
 }
 return _expr.substr(_idx++, 1);
}

std::string ReversePolishNotation::operator()() {
 std::stringstream outExpr;
 std::string word;
 std::string topElem;
 while (true) {
 word = nextWord();
 if (isWord(word)) {
 outExpr << word << " ";
 } else if (isOperator(word)) {
 if (_stk.empty() || _stk.top() == "(") {
 _stk.push(word);
 continue;
 }
 topElem = _stk.top();
 while (getOpPriority(topElem) > getOpPriority(word)) {
 outExpr << topElem << " ";
 _stk.pop();
 if (_stk.empty()) {
  break;
 }
 topElem = _stk.top();
 }
 _stk.push(word);

 } else if (word == "(") {
 _stk.push(word);
 } else if (word == ")") {
 while (true) {
 topElem = _stk.top();
 _stk.pop();
 if (topElem == "(") {
  break;
 }
 assert(!_stk.empty() && "[E]Expr error. Missing '('.");
 outExpr << topElem << " ";
 }
 } else if (word == "") {
 while (!_stk.empty()) {
 topElem = _stk.top();
 assert (topElem != "(" && "[E]Expr error. Redundant '('.");
 outExpr << topElem << " ";
 _stk.pop();
 }
 break;
 } else {
 assert(false && "[W]>>>Can not recognize this word");
 }
 }
 return outExpr.str();
}

int ReversePolishNotation::getOpPriority(const std::string &word) {
 if (word == "+") { return 1; }
 if (word == "-") { return 1; }
 if (word == "*") { return 2; }
 if (word == "/") { return 2; }
 return 0;
}

bool ReversePolishNotation::isWord(const std::string &word) {
 return isalpha(word.c_str()[0]) || isdigit(word.c_str()[0]);
}

bool ReversePolishNotation::isOperator(const std::string &word) {
 return word == "+" ||
  word == "-" ||
  word == "*" ||
  word == "/";
}

/// ---测试代码---
int main() {
 assert(ReversePolishNotation("a+b*c")() == "a b c * + ");
 assert(ReversePolishNotation("(a+b)*c-(a+b)/e")() == "a b + c * a b + e / - ");
 assert(ReversePolishNotation("3*(2-(5+1))")() == "3 2 5 1 + - * ");
// assert(ReversePolishNotation("3*((2-(5+1))")() == "3 2 5 1 + - * "); // Failed Case: Redundant '('
// assert(ReversePolishNotation("3*(?2-(5+1))")() == "3 2 5 1 + - * "); // Failed Case: Can not recognize '?'
 return 0;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C++实现逆波兰式

    (a+b)c的逆波兰式为ab+c,假设计算机把ab+c按从左到右的顺序压入栈中,并且按照遇到运算符就把栈顶两个元素出栈,执行运算,得到的结果再入栈的原则来进行处理,那么ab+c的执行结果如下: 1)a入栈(0位置) 2)b入栈(1位置) 3)遇到运算符"+",将a和b出栈,执行a+b的操作,得到结果d=a+b,再将d入栈(0位置) 4)c入栈(1位置) 5)遇到运算符"",将d和c出栈,执行dc的操作,得到结果e,再将e入栈(0位置) 经过以上运算,计算机就可以得到

  • C++代码实现逆波兰式

    100行以内C++代码实现逆波兰式 逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后). 算术表达式转逆波兰式例子: 逆波兰式整体的算法流程图如下: 下面给出我基于C++ 语言对逆波兰式算法的实现代码,值得注意的是: 1.算法中对操作数,仅支持一个字符的字母或数字的操作数,如:x,y,j,k,3,7等:如果要支持多个字符的操作数,如:var1,3.14等.需要读者自己扩展对算术表达式操作数的分词部分的代码. 2.为了为了增加

  • C语言实现逆波兰式实例

    复制代码 代码如下: #include<stdio.h>#include<string.h> typedef struct{char s[20][20];int top;}SQ; void copystr(char *a,char *b){    int i=0;    do    {        b[i]=a[i];        i++;    }    while(a[i]!='\0');    b[i]='\0';} void voidSQ(SQ *s){    s-&g

  • C++栈实现逆波兰式的应用

    目录 一.定义 二.逆波兰式的意义 三.逆波兰式的实现 1.方法 2.代码实现 一.定义 逆波兰式,又称后缀表达式,指的是操作符在其所控制的操作数后面的表达式. 举个例子,1 + 2 * 3 - 4这个表达式是我们熟悉的中缀表达式,那么其所对应的后缀表达式为:1 2 3 * + 4 -. 再来个复杂的例子:1 * (2 + 3) / 5 - 4 / 2其对应的后缀表达式为:1 2 3 + * 5 / 4 2 / -(其中括号由于只是提升表达式优先级的作用,因此不放入后缀表达式中). 二.逆波兰式

  • PHP使用逆波兰式计算工资的方法

    本文实例讲述了PHP使用逆波兰式计算工资的方法.分享给大家供大家参考.具体如下: 将一个普通的中序表达式转换为逆波兰表达式的一般算法是: 首先需要分配2个栈,一个作为临时存储运算符的栈S1(含一个结束符号),一个作为输入逆波兰 式的栈S2(空栈),S1栈可先放入优先级最低的运算符#,注意,中缀式应以此最低优先级的运算符结束.可指定其他字符,不一定非#不可.从中缀式的左端 开始取字符,逐序进行如下步骤: (1)若取出的字符是操作数,则分析出完整的运算数,该操作数直接送入S2栈:若取出的是运算符,并

  • C++代码实现逆波兰表达式

    本文实例为大家分享了C++实现逆波兰表达式的具体代码,供大家参考,具体内容如下 当我们输入一个数学表达式,是中缀表达式,我们首先转换为后缀表达式(逆波兰表达式),然后再进行求值. 在<大话数据结构>的104-100页有详细的介绍,下面是我理解之后的代码实现. 代码思路: (1)首先对输入的中缀表达式合法性进行判断,bool isStringLegal(const char* str); 函数实现. (2)然后把中缀表达式转换为后缀表达式. (3)根据后缀表达式求出结果,double getTh

  • 逆波兰计算器(Java实现)

    之前的一篇博客中,讲的是用栈实现了中缀表达式的简易计算器,对于我们人来讲,中缀表达式是一种比较直观,而且非常好计算的一种形式,但对于计算器来讲,非常的难去看懂.所以,下面我讲下逆波兰计算器的Java实现. 逆波兰式(后缀表达式) 逆波兰表达式又叫做后缀表达式.逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法 [1]  .后来,人们就把用这种表示法写出的表达式称作"逆波兰表达式".逆波兰表达式把运算量写在前面,把算符写在后面

  • Java实现简易计算器(逆波兰表达式)

    本文实例为大家分享了Java实现简易计算器的具体代码,供大家参考,具体内容如下 程序的运行环境为Windows10 ,编译环境为IDEA. 计算器有以下功能和要求:能够计算复杂表达式,实现对多位数和负数以及小数的多则复杂计算 已完善功能(Bug): 1,能够计算大数字,小数,负数 2,小数点,运算符等不能连续输入(例如 ..,++,**等) 3,小数点前没有数字时自动补0并在输入框显示“0.”若小数点前是数字,且前面的数字串里含有".",则不能继续输入小数点(“.”---”0.“ ,1

  • Java编程实现逆波兰表达式代码示例

    逆波兰表达式 定义:传统的四则运算被称作是中缀表达式,即运算符实在两个运算对象之间的.逆波兰表达式被称作是后缀表达式,表达式实在运算对象的后面. 逆波兰表达式: a+b ---> a,b,+ a+(b-c) ---> a,b,c,-,+ a+(b-c)*d ---> a,b,c,-,d,*,+ a+d*(b-c)--->a,d,b,c,-,*,+ a=1+3 ---> a=1,3 + http=(smtp+http+telnet)/1024 写成什么呢? http=smtp,

  • Python实现处理逆波兰表达式示例

    本文实例讲述了Python实现处理逆波兰表达式.分享给大家供大家参考,具体如下: 中文名: 逆波兰表达式 外文名: Reverse Polish Notation 别名: 后缀表达式 逆波兰表达式又叫做后缀表达式.在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,这种表示法也称为中缀表示.波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法,按此方法,每一运算符都置于其运算对象之后,故称为后缀表示.这个知识点在数据结构和编译原理这两门课程中都有介绍.它的优

随机推荐