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

本文实例为大家分享了C++实现逆波兰表达式的具体代码,供大家参考,具体内容如下

当我们输入一个数学表达式,是中缀表达式,我们首先转换为后缀表达式(逆波兰表达式),然后再进行求值。

在《大话数据结构》的104-100页有详细的介绍,下面是我理解之后的代码实现。

代码思路:

(1)首先对输入的中缀表达式合法性进行判断,bool isStringLegal(const char* str); 函数实现。

(2)然后把中缀表达式转换为后缀表达式。

(3)根据后缀表达式求出结果,double getTheResult(vector<string> &vec);函数实现。

注意:表达式的运算符可以输入 加、减、乘、除、括号,输入的数据为整形数据,计算结果为double型数据。

#include <iostream>
#include <math.h>
#include <map>
#include <vector>
#include <string.h>
#include <memory>
#include <string>
#include <stdio.h>
#include <stack>
#include <stdlib.h>

using namespace std;

#define MAX_STRING_LENGTH 100

/* 解析当前的整形数据,并把整形数据转换为string型 */
string analyData(const char* str, int &i);

/* 根据逆波兰表达式求表达式的值 */
double getTheResult(vector<string> &vec);

/* 判断该字符是否是 + - * / ( ) */
bool isCalChar(const char ch);

/* 判断输入的中缀表达式是否合法 */
bool isStringLegal(const char* str);

/* 解析当前的整形数据,并把整形数据转换为string型 */
string analyData(const char* str, int &i)
{
  int temp = i++;
  while(str[i] >= '0' && str[i] <= '9' && str[i] != '\0')
  {
    i++;
  }

  string s(str+temp,str+i);

  return s;
}

/* 根据逆波兰表达式求表达式的值 */
double getTheResult(vector<string> &vec)
{
  vector<string>::iterator it;
  stack<double> sta;

  string strTemp;
  double d = 0, d1 = 0, d2 = 0;

  for(it = vec.begin(); it != vec.end(); it++)
  {
    strTemp = (*it);

    if(strTemp == "+")
    {
      d1 = sta.top();
      sta.pop();

      d2 = sta.top();
      sta.pop();

      d = d1 + d2;
      sta.push(d);
    }
    else if(strTemp == "-")
    {
      d1 = sta.top();
      sta.pop();

      d2 = sta.top();
      sta.pop();

      d = d2 - d1;
      sta.push(d);
    }
    else if(strTemp == "*")
    {
      d1 = sta.top();
      sta.pop();

      d2 = sta.top();
      sta.pop();

      d = d2 * d1;
      sta.push(d);
    }
    else if(strTemp == "/")
    {
      d1 = sta.top();
      sta.pop();

      d2 = sta.top();
      sta.pop();

      d = d2 / d1;
      sta.push(d);
    }
    else
    {
      const char *p = strTemp.c_str();
      d = atoi(p);
      sta.push(d);
    }
  }
  return sta.top();
}

/* 判断该字符是否是 + - * / ( ) */
bool isCalChar(const char ch)
{
  if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')')
  {
    return true;
  }

  return false;
}
/* 判断输入的中缀表达式是否合法 */
bool isStringLegal(const char* str)
{
  /* 判断是否是空串 */
  if(NULL == str)
  {
    return false;
  }

  int len = strlen(str);
  int i = 0;
  int flag = 0;

  /* 字符串的开头和末尾是否是数字 */
  if(str[0] > '9' || str[0] < '0' || str[len-1] > '9' || str[len-1] < '0')
  {
    return false;
  }

  for(i = 0; str[i] != '\0'; i++)
  {
    /* 是否有除了加减乘除括号之外的字符 */
    if(isCalChar(str[i]) == false)
    {
      return false;
    }

    /* 判断是否有两个连续的符号 */
    if(i < len-1 && isCalChar(str[i]) == true)
    {
      if(isCalChar(str[i+1]) == true)
      {
        return false;
      }

    }

    /* 判断括号是否成对 */
    if(str[i] == '(')
    {
      flag++;
    }
    else if(str[i] == ')')
    {
      flag--;
    }

    /* 判断是否出现 )( 这样的情况 */
    if(flag < 0)
    {
      return false;
    }
  }

  /* 判断括号是否匹配 */
  if(flag != 0)
  {
    return false;
  }

  return true;
}

int main(void)
{
  char str[MAX_STRING_LENGTH] = {0};
  int i = 0;
  string data;

  /* 存放运算符表达式的栈 */
  stack<char> oper_char;

  /* 存放后缀表达式 */
  vector<string> post_str;

  /* 输入中缀的表达式 */
  gets(str);

  /* 判断输入的中缀表达式是否合法 */
  if(isStringLegal(str) != true)
  {
    cout << "This expression is not legal." << endl;
  }
  else
  {
    /* 将中缀表达式转换为后缀表达式 */
    for(i = 0; str[i] != '\0'; i++)
    {
      /* 如果该字符为数字,解析该数字,并压入栈 */
      if(str[i] >= '0' && str[i] <= '9')
      {
        data = analyData(str,i);
        post_str.push_back(data);
        i--;
      }
      else if(str[i] == '(')
      {
        oper_char.push(str[i]);
      }
      else if(str[i] == ')')
      {
        char chtemp[2] = {0};

        chtemp[0] = oper_char.top();

        while(chtemp[0] != '(')
        {
          string strtemp(chtemp);
          post_str.push_back(strtemp);
          oper_char.pop();

          chtemp[0] = oper_char.top();
        }
        oper_char.pop();
      }
      else if(str[i] == '+' || str[i] == '-')
      {
        char chtemp[2] = {0};

        /* 全部出栈,但是碰到 '('就要停止出栈 */
        while(oper_char.size() != 0)
        {
          chtemp[0] = oper_char.top();
          if(chtemp[0] == '(')
          {
            break;
          }

          oper_char.pop();

          string strtemp(chtemp);
          post_str.push_back(strtemp);
        }

        /*将当前的表达式符号入栈*/
        oper_char.push(str[i]);
      }
      else if(str[i] == '*' || str[i] == '/')
      {
        char chtemp[2] = {0};
        while(oper_char.size() != 0)
        {
          chtemp[0] = oper_char.top();
          if(chtemp[0] == '(' || chtemp[0] == '+' || chtemp[0] == '-')
          {
            break;
          }
          else
          {
            oper_char.pop();

            string strtemp(chtemp);
            post_str.push_back(strtemp);
          }
        }

        /*将当前的表达式符号入栈*/
        oper_char.push(str[i]);
      }
    }

    /* 存放表达式的栈可能还有数据 */
    while(!oper_char.empty())
    {
      char chtemp[2] = {0};
      chtemp[0] = oper_char.top();
      oper_char.pop();

      string strtemp(chtemp);
      post_str.push_back(strtemp);
    }

    /* 把逆波兰表达式求值 */
    cout << getTheResult(post_str) << endl;
  }

  return 0;
}

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

(0)

相关推荐

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

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

  • 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++代码实现逆波兰表达式

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

  • 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年提出了另一种表示表达式的方法,按此方法,每一运算符都置于其运算对象之后,故称为后缀表示.这个知识点在数据结构和编译原理这两门课程中都有介绍.它的优

  • C++实现LeetCode(150.计算逆波兰表达式)

    [LeetCode] 150.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. Note: Division between two integ

  • C++实现逆波兰表达式的例题详解

    目录 1. 题目描述 2. 解题思路 3. 动图演示 4. 代码实现 1. 题目描述 2. 解题思路 逆波兰表达式由波兰的逻辑学家卢卡西维兹提出,它的特点是:没有括号,运算符总是放在和它相关的操作数之后.因此,逆波兰表达式也称后缀表达式,它严格遵循「从左到右」的运算. 在我们平时生活中,使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ). 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) . 计算逆波兰表达式的值时,使用一个栈存储操作数,从

  • python实现逆波兰计算表达式实例详解

    本文实例讲述了python实现逆波兰计算表达式的方法.分享给大家供大家参考.具体分析如下: 逆波兰表达式又叫做后缀表达式.在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示.波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法.按此方法,每一运算符都置于其运算对象之后,故称为后缀表示. # -*- coding: utf-8 -*- symbol_priority = {} symbol_priority[0] = ['#']

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

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

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

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

随机推荐