The C++ code implements the inverse Polish expression

Example of this article for you to share C++ inverse Polish expression specific code for your reference, the specific content is as follows

When we enter a mathematical expression that is an infix expression, we first convert it to a postfix expression (an inverse Polish expression), and then evaluate it.

This is described in detail on pages 104-100 of Big Talk Data Structures. Here is the code implementation after I understand it.

Code idea:

(1) First, judge the validity of the infix expression input, bool isStringLegal(const char* str); Function implementation.

(2) Then convert the infix expression to the postfix expression.

(3) Calculate the result according to the postfix expression, double getTheResult(vector) < string > & vec); Function implementation.

Note: The operator of the expression can be added, subtracted, multiplied, divided, parenthesis. The input data is plastic data, and the calculated result is double data.

#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
 
/*  Parse the current shaping data and convert the shaping data to string type  */
string analyData(const char* str, int &i);
 
/*  Evaluate the expression according to the inverse Polish expression  */
double getTheResult(vector<string> &vec);
 
/*  Determine if the character is  + - * / ( ) */
bool isCalChar(const char ch);
 
/*  Determines whether the infix expression entered is valid  */
bool isStringLegal(const char* str);
 
 
 
/*  Parse the current shaping data and convert the shaping data to string type  */
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;
}
 
/*  Evaluate the expression according to the inverse Polish expression  */
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();
}
 
/*  Determine if the character is  + - * / ( ) */
bool isCalChar(const char ch)
{
  if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')')
  {
    return true;
  }
 
  return false;
}
/*  Determines whether the infix expression entered is valid  */
bool isStringLegal(const char* str)
{
  /*  Determines if it is an empty string  */
  if(NULL == str)
  {
    return false;
  }
 
  int len = strlen(str);
  int i = 0;
  int flag = 0;
 
  /*  Whether the beginning and end of a string are Numbers  */
  if(str[0] > '9' || str[0] < '0' || str[len-1] > '9' || str[len-1] < '0')
  {
    return false;
  }
 
 
  for(i = 0; str[i] != '\0'; i++)
  {
    /*  Is there any character other than addition, subtraction, multiplication, and parentheses  */
    if(isCalChar(str[i]) == false)
    {
      return false;
    }
 
    /*  Determine if there are two consecutive symbols  */
    if(i < len-1 && isCalChar(str[i]) == true)
    {
      if(isCalChar(str[i+1]) == true)
      {
        return false;
      }
 
    }
 
    /*  Determine if the parentheses are paired  */
    if(str[i] == '(')
    {
      flag++;
    }
    else if(str[i] == ')')
    {
      flag--;
    }
 
    /*  Judge whether or not  )(  In this case  */
    if(flag < 0)
    {
      return false;
    }
  }
 
  /*  Determine if the parentheses match  */
  if(flag != 0)
  {
    return false;
  }
 
  return true;
}
 
int main(void)
{
  char str[MAX_STRING_LENGTH] = {0};
  int i = 0;
  string data;
 
  /*  A stack that holds operator expressions  */
  stack<char> oper_char;
 
  /*  Store postfix expressions  */
  vector<string> post_str;
 
  /*  Enter an expression for the infix  */
  gets(str);
 
  /*  Determines whether the infix expression entered is valid  */
  if(isStringLegal(str) != true)
  {
    cout << "This expression is not legal." << endl;
  }
  else
  {
    /*  Converts an infix expression to a postfix expression  */
    for(i = 0; str[i] != '\0'; i++)
    {
      /*  If the character is a number , Parse the number and push the stack  */
      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};
 
        /*  All out of the stack, but hit  '(' You're going to stop pushing the stack  */
        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);
        }
 
        /* Pushes the current expression symbol onto the stack */
        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);
          }
        }
 
        /* Pushes the current expression symbol onto the stack */
        oper_char.push(str[i]);
      }
    }
 
    /*  The stack that holds the expression may also have data  */
    while(!oper_char.empty())
    {
      char chtemp[2] = {0};
      chtemp[0] = oper_char.top();
      oper_char.pop();
 
      string strtemp(chtemp);
      post_str.push_back(strtemp);
    }
 
    /*  Evaluate the inverse Polish expression  */
    cout << getTheResult(post_str) << endl;
  }
 
  return 0;
}