实习题目：表达式的后缀表示
一、 上机实习题目与要求
问题描述
表达式的后缀表示：
表达式中包含运算对象、运算符和圆括号等，习惯上使用中缀表示（指运算符夹在两运算符对象中间）形式。计算表达式的值，涉及到运算符的优先级别，如先乘除后加减。括在一对 圆括号中的子表达式必须先计算，因此，圆括号可视为特殊的 运算符，具有最高优先级别。圆括号可以任意嵌套，这意味着 左圆括号后面又是表达式，形成表达式的递归定义。为了直接 指明表达式中各运算对象的先后计算顺序，可将表达式的中缀 形式转换成后缀（指运算符放在二运算对象的后面）形式。例 如，表达式ab-(c+d)/e，这是通常的中缀形式，其后缀表示是 abcd+e/-,其中圆括号在后缀形式中已不见了。
设计一转换程序，将输入的任一表达式转换成相应的后缀形 式后输出。
基本要求
为简单起见，假定运算对象只含变量，且每个变量名以单字母 表示；运算符仅含+、-、*、/和圆括号；表达式以分号“；”结尾。在 转换过程中，要求作必要的语法检查，例如圆括号是否配对，单词 是否合法等。
要求分别编写转换程序的非递归与递归算法。
二、数据结构设计
选择栈作为运算符作为运算符的存储结构。
对于一个表达式，从左到右依次扫描时并不能确定当前运算符的优先级，在右边可能存在优先级更高的运算符，因此需要一个栈将运算符暂时存下来，而且当需要这个运算符的，恰好要的是最后存储的那个运算符，与栈的定义完全相同，因此可以选择栈作为运算符的临时存储结构。
三、源代码
stdfax.h
#ifndef STDFAX_H_INCLUDE
#define STDFAX_H_INCLUDE
#include <iostream>
#include <string>
#include <cstring>
#include <stdio.h>
#include <assert.h>
using namespace std;
#endif // !SYDFAX_H_INCLUDEpostfix.h
#ifndef POSTFIX_H_INCLUDED
#define POSTFIX_H_INCLUDED
#include "stdfx.h"
template <class T>
//栈类
class Stack
{
private:
T* elements; //存放元素的栈数组
int top; //栈顶指针
int maxSize; //栈能容纳元素的最大个数
public:
//构造函数
Stack(int sz = 50) :top(-1), maxSize(sz)
{
//创建一个元素个数为maxSize的数组
elements = new T[maxSize];
assert(elements != NULL);
}
~Stack() { delete[] elements; } //析构函数
//栈扩充函数
void overflow()
{ //每次扩充20个元素
const int add = 20;
T* newArray = new T[maxSize + add];
if (newArray == NULL)
{
cerr << "存储分配失败！" << endl;
exit(1);
for (int i=0;i<=top;i++)
{ //将旧栈的元素移动到新栈中
newArray[i] = elements[i];
}
}
//复制完毕后释放原来栈的空间，最大容纳量增加
maxSize += add;
delete[] elements;
}
//判断栈是否为空
bool Empty() const { return (top == -1) ? true : false; }
//判断栈是否为满
bool Full() const { return (top == maxSize - 1) ? true : false; }
//获取栈顶元素的值
T Top() const
{ return elements[top]; }
//进栈函数
void Push(T& value) { elements[++top] = value;}
//出栈函数
T Pop() { return elements[top--]; }
};
//判断字符是否合法
bool legal(char ch)
{
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == ';'
|| ch == ')' || ch == '(' || isdigit(ch) || isalpha(ch) )
return true;
else return false;
}
//判断括号是否匹配
bool MatchPairs(string& equation)
{
Stack<int> s; //存储括号
int len = equation.length();
for (int i = 0;i < len;i++)
{
if (equation[i] == '(') s.Push(i);
else if (equation[i] == ')')
{
if (s.Empty())
{
cout << "括号不匹配！" << endl;
return false;
}
else { s.Pop(); }
}
}
while (!s.Empty())
{
cout << "括号不匹配！" << endl;
return false;
}
return true;
}
//优先级排序
int priority(char ch)
{
if (ch == '(') return 0;
if (ch == '+' || ch == '-') return 1;
if (ch == '*' || ch == '/') return 2;
else return -1;
}
//中缀表达式转化为后缀表达式的非递归算法
string change1(string& equation)
{
string postfix=""; //字符串str1为后缀表达式
Stack<char> opera; //定义一个char类型的栈opera用于存储运算符
if (MatchPairs(equation) == false)
{
cout << "输入的表达式括号不匹配！" << endl;
return "error";
}
//依次处理每个字符
for (char ch : equation)
{
if (legal(ch) == false)
{
//先判断字符是否合法
cout << "输入的表达式不合法！" << endl;
break;
}
//为结束标识符'；'退出循环操作
if (ch == ';')
break;
//如果是数字或字母，直接进入后缀表达式
if (isdigit(ch) || isalpha(ch))
{
postfix += ch;
}
else { //否则为运算符
if (ch == '(') //如果是左括号，入栈
opera.Push(ch);
else if (ch == ')')
{ //如果是右括号，但栈顶不是左括号，就依次弹出并加入到后缀表达式，直到为左括号
while (opera.Top() != '(')
{
postfix += opera.Top();
opera.Pop();
}
opera.Pop(); //弹出左括号，但不输出
}
else
{
while (priority(ch) <= priority(opera.Top()))
{ //栈顶优先级大于等于当前运算符，则输出
postfix += opera.Top();
opera.Pop();
if (opera.Empty()) //如果栈为空，停止输出
break;
}
opera.Push(ch); //把当前运算符入栈
}
}
}
while (opera.Empty()==false)
{ //最后，如果栈不空，则弹出所有元素并输出
postfix += opera.Top();
opera.Pop();
}
return postfix;
}
//中缀表达式转化为后缀表达式的递归算法
string postfix = ""; //字符串str1为后缀表达式
Stack<char> opera; //定义一个char类型的栈opera用于存储运算符
string change2(string& equation)
{
if (equation.length() == 0)
return postfix;
string temp = equation.substr(1);
//如果是数字或字母，直接进入后缀表达式
if (equation.length() == 0)
return postfix;
char ch = equation.at(0);
if (isdigit(ch) || isalpha(ch))
{
postfix += ch;
return change2(temp);
}
else
{ //否则为运算符
if (ch == '(') //如果是左括号，入栈
{
opera.Push(ch);
return change2(temp);
}
else if (ch == ')')
{ //如果是右括号，但栈顶不是左括号，就依次弹出并加入到后缀表达式，直到为左括号
while (opera.Top() != '(')
{
postfix += opera.Top();
opera.Pop();
}
opera.Pop(); //弹出左括号，但不输出
return change2(temp);
}
else
{
while (priority(ch) <= priority(opera.Top()))
{ //栈顶优先级大于等于当前运算符，则输出
postfix += opera.Top();
opera.Pop();
if (opera.Empty()) //如果栈为空，停止输出
break;
}
opera.Push(ch); //把当前运算符入栈
return change2(temp);
}
}
}
string print(string& postfix)
{
while (opera.Empty() == false)
{
//最后，如果栈不空，则弹出所有元素并输出
postfix += opera.Top();
opera.Pop();
}
return postfix;
}
#endif // !POSTFIX_H_INCLUDEDmain.cpp
#include "postfix.h"
#include "stdfx.h"
int main() {
string infix;
string postfix;
cout << "请输入中缀表达式：" << infix;
cin >> infix;
postfix=change1(infix);
cout << "非递归后缀表达式为：" << postfix << endl;
postfix = change2(infix);
postfix = print(postfix);
cout << "递归后缀表达式为：" << postfix << endl;
system("pause");
return 0;
}
