【数据结构】——中缀表达式求值
题目要求
从键盘输入中缀表达式，创建操做数与运算符堆栈，计算并输出表达式的求值结果。
基本要求：实现 +, -, *, /四个二元运算符以及（）；操做数范围为0至9。
提升要求：实现+, -两个一元运算符（即正、负号）；操做数可为任意整型值（程序可不考虑计算溢出）。
若两个整数相除，结果只保留整数商（余数丢弃）；可不处理表达式语法错误。ios
涉及知识点
栈与队列算法
数据结构设计
采用C++的模板类，分别建立元素类型为整型的操做数栈OPND和字符型的运算符栈OPTR，每一个栈对象中，elem指针用来创建长度为n的数组，n表示栈中元素的最大个数，top表示栈顶指针。数组
算法描述
①中缀表达式以'#'结束，'#'字符也作运算符处理。
②'('、')'做为运算符处理，括号内运算结束后须要消除括号。
③须要创建两个不一样类型的栈，整型的操做数栈OPND和字符型的运算符栈OPTR。
④算法主要步骤：
a. 初始时，OPND置空，'#'做为OPTR栈底元素；
b. 依次读入表达式中的每一个字符，如果操做数，直接压入OPND栈；
c. 如果运算符(记为θ)，PTR栈顶运算符(为λ)优先级；
λ<θ，θ压入OPTR栈，继续读下一个字符；
λ=θ，脱括号，继续读下一个字符；
λ>θ，执行λ运算（λ退栈），θ等在栈外（不读下一个字符），即θ继续和OPTR 栈顶运算符比较优先级（重复进行以上操做），直至θ能入栈。
⑤对于一元运算符（即正、负号），用'P'表明'+'，'N'表明'-'。数据结构
程序代码
#include<iostream>
using namespace std;
template <typename T>
class Stack //模板类:栈
{
public:
Stack(); //默认构造函数
Stack(int n); //构造函数,调用函数createStack(int n),建立长度为n的栈
~Stack(); //虚构函数
int createStack(int n); //建立长度为n的栈
int empty(); //判断栈是否为空
int full(); //判断栈是否为满
int push(T e); //将元素e压栈
int pop(T &e); //元素出栈，保存在e中
T get_top(); //获得栈顶元素
friend int isoperator(char &e);//判断字符e是否为运算符
friend int isp(char &e);//返回栈中运算符的优先级
friend int icp(char &e);//返回栈外运算符的优先级
friend int compute(int x, char a, int y);//求值函数
private:
T *elem; //创建长度为n的数组
int n; //栈中元素的最大个数
int top; //栈顶指针
};
template<typename T>
Stack<T>::Stack()
{
top = -1;
}
template<typename T>
Stack<T>::Stack(int n)
{
createStack(n);
}
template<typename T>
Stack<T>::~Stack()
{
n = 0;
top = -1;
delete[]elem;
}
template<typename T>
int Stack<T>::createStack(int n)
{
if (n <= 0)
return 0;
this->n = n;
top = -1;
elem = new T[n];
if (!elem)
return 0;
return 1;
}
template<typename T>
int Stack<T>::empty()
{
return top == -1;
}
template<typename T>
int Stack<T>::full()
{
return top >= n - 1;
}
template<typename T>
int Stack<T>::push(T e)
{
if (top >= n - 1)
return 0;
elem[++top] = e;
return 1;
}
template<typename T>
int Stack<T>::pop(T & e)
{
if (top == -1)
return 0;
e = elem[top--];
return 1;
}
template<typename T>
T Stack<T>::get_top()
{
return elem[top];
};
int isoperator(char &e) //判断是否为运算符
{
if (e == '+' || e == '-' || e == '*' || e == '/' || e == '(' || e == ')' || e == '#' || e == 'P' || e == 'N')
return 1; //是运算符返回1
else
return 0; //不是运算符返回0
}
int isp(char &e) //返回栈中运算符的优先级
{
switch (e)
{
case '#':
return 0; break;
case '(':
return 1; break;
case '+':
case '-':
return 2; break;
case '*':
case '/':
return 3; break;
case 'P':
case 'N':
return 4; break;
case ')':
return 5; break;
default:
return -1; break;
}
}
int icp(char &e) //返回栈外运算符的优先级
{
switch (e)
{
case '#':
return 0; break;
case ')':
return 1; break;
case '+':
case '-':
return 2; break;
case '*':
case '/':
return 3; break;
case 'P':
case 'N':
return 4; break;
case '(':
return 5; break;
default:
return -1; break;
}
}
int compute(int x, char a, int y)
{
switch (a)
{
case '+': //计算加法
return x + y; break;
case '-': //计算减法
return x - y; break;
case '*': //计算乘法
return x * y; break;
case '/': //计算除法
return x / y; break;
default:
return -1; break;
}
}
int g1()
{
char a, b, c;
int i, j, f, value, firstOpnd, secondOpnd, m;
Stack<char> OPTR(MAX); //创建运算符栈
Stack<int> OPND(MAX); //创建操做数栈
OPTR.push('#'); //'#'压栈
cout << "请输入中缀表达式： ";
a = getchar();
while (a != '#' || OPTR.get_top() != '#')
{
if (!isoperator(a)) //不是运算符，即为操做数，操做数入栈
OPND.push(a - 48);//将字符型转化为整型数字
else //是运算符，与栈顶运算符比较优先级大小
{
b = OPTR.get_top();//获得栈顶元素
i = isp(b); //栈顶运算符的优先级
j = icp(a); //栈外运算符的优先级
if (i < j) //栈外运算符优先级高，运算符入栈
OPTR.push(a);
else
{
OPTR.pop(b);
if (b != '('&&i == j || i > j)
{
c = OPTR.get_top();
if ((c == '(' || c == '#') && (b == 'P' || b == 'N')) /*c为一元运
算符：正负号*/
{
OPND.pop(firstOpnd); //获得操做数
switch (b)
{
case 'P': //正号
f = firstOpnd * 1;
break;
case 'N': //负号
f = firstOpnd * (-1);
break;
}
}
else //c为二元运算符
{
OPND.pop(secondOpnd); //获得第二操做数
OPND.pop(firstOpnd); //获得第一操做数
f = compute(firstOpnd, b, secondOpnd); //计算求值
}
OPND.push(f); //求值结果压栈
continue;
}
}
}
c = a;
a = getchar(); //继续读取字符
while(!isoperator(a) && !isoperator(c)) /*若连续读取字符均为数字，则乘以位权
获得多位数*/
{
OPND.pop(m);
m = m * 10 + a - 48;
OPND.push(m);
c = a;
a = getchar();
}
}
OPND.pop(value);
return value; //返回表达式的结果
}
int main()
{
int a;
a = g1();
cout << "运算结果为: " << a << endl;
return 0;
}
示例
（1）程序输入：3+5*(9-5)/10#
程序输出：5
函数
（2）程序输入：P9+10*(N2*8/4)-10#
程序输出：-41
this
（3）程序输入：20-3*25+(N41/3)*100#
程序输出：-1355
spa