中缀算术表达式求值(超详细代码)

• 算法使用的主要数据结构和实现的基本思路

1. 数据结构

由于是求表达式值的过程, 所以要用栈数据结构

由于是有运算符和数字两个对象, 所以要用两个栈来存储

        2. 算法

遇到各节点后的处理

1. 数字

数字并不会产生计算过程, 所以只需提取数字, 将数字压栈

1. 括号

括号分为两个运算符 ( 和 )

遇到 ‘( ‘说明会往下走, 所以只需将 ‘(‘ 压栈

遇到 ‘)’ 说明会往上走, 所以要计算括号表示的子树的结果, 所以要逆向计算运算符直至遇到 (

1. 普通二元运算符

如果当前运算符优先级比上一运算符高, 说明是往下走, 则只需将运算符压栈

如果当前运算符优先级比上一运算符低, 说明是往上走, 则需要一直计算上一运算符直至当前运算符优先级比上一运算符高

• 具体代码

注：因为要创建俩个不同类型的栈，所以使用C++里的模板函数

创建栈：

#define INIT_SIZE 10

template
class stack{
    private:
        T* base;
        int tt;
        int size;
    protected:
        void init(){base=new T[INIT_SIZE],tt=-1,size = INIT_SIZE;}
        void expand()
        {
            T* old=base;
            base=new T[size<<1];//容量倍增
            for(int i=0;isize)  expand();
            base[++tt]=e;
        }
        //出栈
        bool pop()
        {
            if(empty()) return false;
            tt--;
            return true;
        }
        //返回端顶元素
        T top()
        {
            return base[tt];
        }
        int Getsize(){return tt;}
};

将栈定义放入头文件MyStack.h中

主函数

//表达式求值
#include 
#include 
#include "MyStack.h"
using namespace std;

stack num; //创建数值栈
stack op;    //创建字符栈

void eval();                              //取出num与op进行运算
int prop(char c);                         //得到运算符优先级
void judge(const string &str, int &i);    //根据字符判断进行哪一步操作
void ReadNumber(const string str, int &i); //根据字符串读入数值
bool isNumber(const string &str, int &i); //判断是否为数字
bool isNegative(const string &str,const int &i);//判断是否为负数

int main()
{
  //读入字符串
  string str;
  printf("请输入中缀表达式：n");
  getline(cin, str);

  printf("操作数栈栈顶元素变化：n");
  for (int i = 0; i < str.size(); i++)
    judge(str, i);

  while (!op.empty())
    eval();

  printf("表达式的结果为：%.2lf ", num.top());

  return 0;
}

函数实现

void eval()
{
  //取出数值并运算 顺序不能变！！！
  double b = num.top();num.pop();
  double a = num.top();num.pop();
  char c = op.top();op.pop();
  //做运算
  double x = 0;
  if (c == '+')       x = a + b;
  else if (c == '-')  x = a - b;
  else if (c == '*')  x = a * b;
  else if (c == '/')  x = a / b;
  else if (c == '^')  x = pow(a, b);
  else if (c == '%')  x = (int)a % (int)b;

  num.push(x);                  //结果压入值栈
  printf("%.2lfn", num.top()); //栈顶元素变化
}
int prop(char c)
{
  int pr;
  switch (c)
  {
  case '+': pr = 1;break;
  case '-': pr = 1;break;
  case '*': pr = 2;break;
  case '/': pr = 2;break;
  case '%': pr = 2;break;
  case '^': pr = 3;break;
  default:  pr = 0; //括号的优先级为0
  }
  return pr;
}
bool isNegative(const string &str,const int &i)
{
  //判断是否为负数
  if (i == 0 && str[i] == '-' && isdigit(str[i + 1]))
    return true;
  else if (str[i] == '-' && !isdigit(str[i - 1]) && isdigit(str[i + 1]))
    return true;

  return false;
}
void ReadNumber(const string str, int &i)
{
  //j与k用来计数，flag用来得到负数
  int j = i, k = 1, flag = 1;
  double x = 0;
  //判断是否为负
  if (isNegative(str, i))
    flag = -1, j++;

  while (j < str.size() && (isdigit(str[j]) || str[j] == '.'))
  {
    if (isdigit(str[j]))
      x = x * 10 + flag * (str[j++] - '0');//读入整数
    else if (str[j] == '.')
    {
      j++;
      x = x + pow(10, -(k++)) * (double)(str[j++] - '0'); //读入小数
    }
  }
  i = j - 1; //因为循环结束后会执行一次j++,所以应该把j-1赋给i
  num.push(x);
  printf("%.2lfn", num.top());
}
void judge(const string &str, int &i)
{
  char c = str[i]; //得到当前字符

  if (c == ' '){return;} //特判空格

  if (isNegative(str, i) || isdigit(str[i])) //如果c是数字，就读入然后存入栈中
      ReadNumber(str, i);
  else if (c == '(') //如果读入左括号，直接压入字符栈
      op.push(c);
  else if (c == ')') //如果读入右括号，不断运算直至遇到匹配的左括号
  {
    while (op.top() != '(')
      eval();
    op.pop();
  }
  else
  {
    // op的优先级要高于c中top的优先级
    while (!op.empty() && op.top() != '(' && prop(op.top()) > prop(c))
      eval();
    op.push(c); //把当前运算符入栈
  }
}

运行结果

输入：测试样例一：3+5^2+3/5+9/3+(3+5)*3

测试样例二：10+(3+2)^4

测试样例三：-5+14/(-3+5*2)

• 时间复杂度与空间复杂度分析

此算法从头到尾扫描表达式中每个字符，若表达式的字符串长度为n，读入数字时的循环次数几乎可忽略不计，则此算法的时间复杂度为

O（n）。算法在运行时所占的辅助空间主要取决于num数值栈和op字符栈的大小，他们的空间大小之和不会超过n，所以此算法的空间复杂度也同样为O（n）。