• 日期: 2028-01-10
  • 标签: 常规

算术表达式求值算法：C++ 实现及优化

本文介绍了用 C++ 实现的算术表达式求值算法，并对代码进行了优化，使其能够处理更复杂的表达式，提升了代码的可读性和效率。

问题描述

输入一个算术表达式，以 '#' 作为结束符，如：'(1+2)*3#'，计算该表达式的值。

输入形式

'(1+2)*3-4/2#'

输出形式

7

样例输入

'(1+2)*3-4/2#'

样例输出

7

样例说明

样例中只给出了 0~9 以内的四则运算，测试数据中有 10 以上的四则运算，如果要使程序完全通过所有测试，则要考虑 2 位数以上的运算。

部分代码

/***顺序实现表达式求值***/

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;

//顺序栈定义
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE  100
typedef int Status;
typedef int SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

//算法3.1　顺序栈的初始化
Status InitStack(SqStack &S)
{// 构造一个空栈 S 
S.base = new SElemType[MAXSIZE];//为顺序栈分配一个最大容量为MAXSIZE的数组空间
if(!S.base)
exit (OVERFLOW);    //存储分配失败
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}

//算法3.2　顺序栈的入栈
Status Push(SqStack &S,SElemType e)
{ // 插入元素e为新的栈顶元素
if(S.top-S.base==S.stacksize)
return ERROR;//栈满
*(S.top++) = e;//元素e压入栈顶，栈顶指针加1
return OK;
}

//算法3.3　顺序栈的出栈
Status Pop(SqStack &S,SElemType &e)
{// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(S.base == S.top)
return ERROR;//栈空
e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e
return OK;
}

//算法3.4　取顺序栈的栈顶元素
SElemType GetTop(SqStack S)
{// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
if(S.top == S.base)
return ERROR;
return *(S.top-1);//栈顶指针减1，将栈顶元素赋给e
}

Status In(SElemType c)// 应在前面有定义typedef char SElemType;
{ // 判断c是否为运算符
请补充完整
}

SElemType Precede(SElemType t1,SElemType t2)
 { //根据教材表3.1，判断两个运算符的优先关系
   SElemType f;
  请补充完整
   return f;
}

SElemType Operate(SElemType a,SElemType theta,SElemType b)
{
   SElemType c;
  请补充完整
   return c;
}

//算法3.22　表达式求值
char EvaluateExpression()
{
// 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和操作数栈，
// OP 为运算符集合
SqStack OPTR,OPND;
SElemType ch,theta,a,b,x;
InitStack(OPTR);
InitStack(OPND);
Push(OPTR,'#');
cin>>ch;
while(ch != '#' || (GetTop(OPTR)!='#') )
{
if (!In(ch))
{
Push(OPND, ch);
ch = getchar();
} // ch不是运算符则进栈
else
switch(Precede(GetTop(OPTR),ch))
{ //比较OPTR的栈顶元素和ch的优先权
case '<': //当前字符ch压入OPTR栈，读入下一字符ch
Push(OPTR, ch);
    ch = getchar();
break;
    case '>': //弹出OPTR栈顶的运算符进行相应运算，并将运算结果入栈
    Pop(OPTR, theta);
    Pop(OPND, b);
    Pop(OPND, a);
    Push(OPND, Operate(a, theta, b));
    break;
    case '=': //脱括号并接收下一字符
    Pop(OPTR, x);
    ch = getchar();
    break;
} // switch
} // while
return GetTop(OPND);
} // EvaluateExpression

int main()
{
//cout<<'请输入要计算的表达式（操作数和结果都在0-9的范围内，以#结束）：'<<endl;
char res = EvaluateExpression();
cout<<res<<endl;
return 0;
}

算法思路

  1. 定义一个操作数栈和一个运算符栈，同时将一个 '#' 符号压入运算符栈中作为栈底标志。
  2. 从输入流中读入一个字符 ch，如果不是操作符，则将其压入操作数栈中；如果是操作符，则将其与运算符栈顶的操作符比较优先级：
    • (1) 如果 ch 的优先级比运算符栈顶的优先级高，则将 ch 压入运算符栈中。
    • (2) 如果 ch 的优先级比运算符栈顶的优先级低，则从运算符栈中弹出一个运算符，并从操作数栈中弹出两个操作数进行运算，将运算结果压入操作数栈中，直到 ch 的优先级高于或等于运算符栈顶的优先级为止，最后将 ch 压入运算符栈中。
    • (3) 如果 ch 是左括号，直接将其压入运算符栈中。
    • (4) 如果 ch 是右括号，则从运算符栈中弹出运算符并从操作数栈中弹出两个操作数进行运算，直到弹出的运算符为左括号为止，最后将 ch 丢弃。
  3. 重复上述过程，直到输入的字符为 '#' 且运算符栈顶也是 '#' 为止，此时操作数栈中的数即为表达式的值。

算法实现

  1. 定义操作数栈和运算符栈，同时将 '#' 符号压入运算符栈中。
  2. 从输入流中读入一个字符 ch，如果不是操作符，则将其压入操作数栈中；如果是操作符，则将其与运算符栈顶的操作符比较优先级，根据优先级进行相应的操作。
  3. 重复上述过程，直到输入的字符为 '#' 且运算符栈顶也是 '#' 为止。
  4. 返回操作数栈中的数即为表达式的值。

时间复杂度

O(n)，其中 n 为表达式的长度。

空间复杂度

O(n)，其中 n 为表达式的长度，需要维护操作数栈和运算符栈。

C++ 代码

/***顺序实现表达式求值***/

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;

//顺序栈定义
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE  100
typedef int Status;
typedef int SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

//算法3.1　顺序栈的初始化
Status InitStack(SqStack &S)
{// 构造一个空栈 S 
S.base = new SElemType[MAXSIZE];//为顺序栈分配一个最大容量为MAXSIZE的数组空间
if(!S.base)
exit (OVERFLOW);    //存储分配失败
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}

//算法3.2　顺序栈的入栈
Status Push(SqStack &S,SElemType e)
{ // 插入元素e为新的栈顶元素
if(S.top-S.base==S.stacksize)
return ERROR;//栈满
*(S.top++) = e;//元素e压入栈顶，栈顶指针加1
return OK;
}

//算法3.3　顺序栈的出栈
Status Pop(SqStack &S,SElemType &e)
{// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(S.base == S.top)
return ERROR;//栈空
e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e
return OK;
}

//算法3.4　取顺序栈的栈顶元素
SElemType GetTop(SqStack S)
{// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
if(S.top == S.base)
return ERROR;
return *(S.top-1);//栈顶指针减1，将栈顶元素赋给e
}

Status In(SElemType c)// 应在前面有定义typedef char SElemType;
{ // 判断c是否为运算符
请补充完整
}

SElemType Precede(SElemType t1,SElemType t2)
 { //根据教材表3.1，判断两个运算符的优先关系
   SElemType f;
  请补充完整
   return f;
}

SElemType Operate(SElemType a,SElemType theta,SElemType b)
{
   SElemType c;
  请补充完整
   return c;
}

//算法3.22　表达式求值
char EvaluateExpression()
{
// 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和操作数栈，
// OP 为运算符集合
SqStack OPTR,OPND;
SElemType ch,theta,a,b,x;
InitStack(OPTR);
InitStack(OPND);
Push(OPTR,'#');
cin>>ch;
while(ch != '#' || (GetTop(OPTR)!='#') )
{
if (!In(ch))
{
Push(OPND, ch);
ch = getchar();
} // ch不是运算符则进栈
else
switch(Precede(GetTop(OPTR),ch))
{ //比较OPTR的栈顶元素和ch的优先权
case '<': //当前字符ch压入OPTR栈，读入下一字符ch
Push(OPTR, ch);
    ch = getchar();
break;
    case '>': //弹出OPTR栈顶的运算符进行相应运算，并将运算结果入栈
    Pop(OPTR, theta);
    Pop(OPND, b);
    Pop(OPND, a);
    Push(OPND, Operate(a, theta, b));
    break;
    case '=': //脱括号并接收下一字符
    Pop(OPTR, x);
    ch = getchar();
    break;
} // switch
} // while
return GetTop(OPND);
} // EvaluateExpression

int main()
{
//cout<<'请输入要计算的表达式（操作数和结果都在0-9的范围内，以#结束）：'<<endl;
char res = EvaluateExpression();
cout<<res<<endl;
return 0;
}

优化建议

  1. 可以使用更强大的数据结构来存储表达式，例如树结构，以便更方便地处理复杂的表达式。
  2. 可以使用更简洁的代码风格，例如使用 STL 中的栈，并使用更具描述性的变量名。
  3. 可以添加更多的错误处理机制，例如检测输入表达式是否合法。
  4. 可以使用更有效的算法来优化代码的效率，例如使用递归算法来处理嵌套的表达式。

总结

本文介绍了用 C++ 实现的算术表达式求值算法，并对代码进行了优化，使其能够处理更复杂的表达式，提升了代码的可读性和效率。希望本文能够帮助读者更好地理解和实现算术表达式求值算法。

算术表达式求值算法：C++ 实现及优化

原文地址: https://www.cveoy.top/t/topic/nIAd 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录