算术表达式求值：使用栈实现表达式计算

本文将介绍如何使用栈数据结构实现算术表达式的求值。算术表达式求值是一个经典的算法问题，它在编译器、解释器等领域有着广泛的应用。

问题描述

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

输入形式

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

输出形式

样例输入

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

样例输出

样例说明

样例中只给出了 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是否为运算符
   if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')
       return 1;
   else
       return 0;
}

SElemType Precede(SElemType t1,SElemType t2)
 { //根据教材表3.1，判断两个运算符的优先关系
   SElemType f;
   switch(t2)
   {
       case '(': 
           if(t1=='#')
               return ERROR;
           else
               return '<';
           break;
       case '+': 
       case '-':
           if(t1=='(')
               return '<';
           else
               return '>';
           break;
       case '*':
       case '/':
           if(t1=='*'||t1=='/'||t1==')')
               return '>';
           else
               return '<';
           break;
       case ')':
           if(t1=='(')
               return '=';
           else
               return '>';
           break;
       case '#':
           if(t1=='#')
               return '=';
           else
               return '>';
           break;
   }
   return f;
}

SElemType Operate(SElemType a,SElemType theta,SElemType b)
{
   SElemType c;
   switch(theta)
   {
       case '+': 
           c=a+b;break;
       case '-':
           c=a-b;break;
       case '*':
           c=a*b;break;
       case '/':
           c=a/b;break;
   }
   return c;
}

//算法3.22　表达式求值
SElemType 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-'0');
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;
SElemType res = EvaluateExpression();
cout<<res<<endl;
return 0;
}

代码解释

数据结构：使用两个栈，OPTR 用于存储运算符，OPND 用于存储操作数。
算法：
- 初始化两个栈，并将 '#' 压入 OPTR 栈作为结束标记。
- 从输入流中读取字符 ch。
- 如果 ch 不是运算符，则将其转换成整数后压入 OPND 栈。
- 如果 ch 是运算符，则比较 ch 与 OPTR 栈顶元素的优先级：
  - 若 ch 的优先级小于栈顶元素，则弹出 OPTR 栈顶运算符，从 OPND 栈中弹出两个操作数进行运算，并将运算结果压入 OPND 栈。
  - 若 ch 的优先级大于栈顶元素，则将 ch 压入 OPTR 栈。
  - 若 ch 与栈顶元素优先级相等，则弹出 OPTR 栈顶元素，并读取下一个字符。
循环结束条件：当 ch 为 '#' 且 OPTR 栈顶元素也为 '#' 时，循环结束。
结果：OPND 栈顶元素即为表达式的结果。

注意事项

代码中使用 getchar() 函数读取字符，需要在编译时添加 -std=c++11 或 -std=c++14 选项。
本代码只处理了单精度整数运算，如果需要处理浮点数或其他运算符，需要修改代码。
在实际应用中，为了提高代码的可读性和可维护性，可以将代码进行模块化，并添加错误处理机制。

总结

使用栈数据结构可以有效地实现算术表达式的求值。该算法简单易懂，并且能够处理各种类型的算术表达式。希望本文能够帮助读者更好地理解和应用栈数据结构。