#define STACKINCREMENT 2 /* 存储空间分配增量 */
typedef struct SqStack
{
SElemType *base/* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top/* 栈顶指针 */
int stacksize/* 当前已分配的存储空间，以元素为单位 */
}SqStack/* 顺序栈 */
Status InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))
if(!(*S).base)
exit(OVERFLOW)/* 存储分配失败 */
(*S).top=(*S).base
(*S).stacksize=STACK_INIT_SIZE
return OK
}
Status GetTop(SqStack S,SElemType *e)
{ /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
if(S.top>S.base)
{
*e=*(S.top-1)
return OK
}
else
return ERROR
}
Status Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base==(*S).stacksize) /* 栈满 */
return ERROR
*((*S).top)++=e
return OK
}
Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR
*e=*--(*S).top
return OK
}
#include<stdio.h>
#include<stdlib.h>/* atoi() */
#include<math.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean/* Boolean是布尔类型,其值是TRUE或FALSE */
/* 表达式求值(范围为int类型,输入负数要用(0-正数)表示) */
typedef int SElemType/* 栈元素类型为整型,改进算法3.4 */
#include"stack.h"
SElemType Precede(SElemType t1,SElemType t2)
{ /* 根据教科书表3.1，判断两符号的优先关系 */
SElemType f
switch(t2)
{
case '+':
case '-':if(t1=='('||t1=='=')
f='<'
else
f='>'
break
case '*':
case '/':if(t1=='*'||t1=='/'||t1==')')
f='>'
else
f='<'
break
case '(':if(t1==')')
{
printf("ERROR1\n")
exit(ERROR)
}
else
f='<'
break
//将此函数补充完整
//......
return f
}
Status In(SElemType c)
{ /* 判断c是否为运算符 */
switch(c)
{
case'+':
case'-':
//将此函数补充完整
//......
}
}
SElemType Operate(SElemType a,SElemType theta,SElemType b)
{
SElemType c
switch(theta)
{
case'+':c=a+b
break
//将此函数补充完整
//......
}
return c
}
SElemType EvaluateExpression()
{ /* 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈 */
SqStack OPTR,OPND
SElemType a,b,d,x,theta
char c/* 存放由键盘接收的字符串 */
char z[6]/* 存放整数字符串 */
int i
InitStack(&OPTR)/* 初始化运算符栈 */
Push(&OPTR,'=')/* =是表达式结束标志 */
InitStack(&OPND)/* 初始化运算数栈 */
c=getchar()
GetTop(OPTR,&x)
while(c!='='||x!='=')
{
if(In(c)) /* 是7种运算符之一 */
switch(Precede(x,c))
{
case'<':Push(&OPTR,c)/* 栈顶元素优先权低 */
c=getchar()
break
//将此函数补充完整
//......
}
else if(c>='0'&&c<='9') /* c是操作数 */
{
//将此函数补充完整
//......
}
else /* c是非法字符 */
{
printf("ERROR3\n")
exit(ERROR)
}
GetTop(OPTR,&x)
}
GetTop(OPND,&x)
return x
}
void main()
{
printf("请输入算术表达式,负数要用(0-正数)表示,并以=结束\n")
printf("%d\n",EvaluateExpression())
}
思路：中缀表达式－后缀表达式－求值参考代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iterator>
#include <algorithm>
// 堆栈的数组实现，数组的大小固定。
template<class T>
class stack
{
private:
T *s // 数组的首地址（栈底）
size_t N // 指向栈顶第一个空闲块
const size_t size// 堆栈的大小，固定不变
public:
stack(size_t n) : size(n)
{
s = new T[n]// 可能抛出异常
N = 0 // 设置栈顶指针
}
~stack()
{
delete [] s
}
bool empty() const
{
return N == 0
}
bool full() const
{
return N == size
}
void push(const T &object)
{
if (full())
{
throw "error: stack is full !"
}
s[N++] = object
}
T pop()
{
if (empty())
{
throw "error: stack is empty !"
}
return s[--N]
}
T peek() const
{
if (empty())
{
throw "error: stack is empty !"
}
return s[N-1]
}
friend std::ostream&operator<<(std::ostream&os, const stack<T>&stk)
{
for (size_t i = 0i <stk.Ni++)
{
std::cout <<stk.s[i] <<" "
}
return os
}
}
// 堆栈的链表实现
template<class T>
class STACK
{
private:
typedef struct node
{
T item
node *next
node(T x, node *t = NULL) : item(x), next(t) {}
}*link
link head // 指向栈顶第一个有效对象
public:
STACK(size_t n)
{
head = NULL
}
~STACK() // 也可以用pop的方法删除，但效率低
{
link t = head
while (t != NULL)
{
link d = t
t = t->next
delete d
}
}
bool empty() const
{
return head == NULL
}
bool full() const
{
return false
}
void push(const T &object)
{
head = new node(object, head)
}
T pop()
{
if (empty())
{
throw "error: stack is empty !"
}
T v = head->item
link t = head->next
delete head
head = t
return v
}
T peek() const
{
if (empty())
{
throw "error: stack is empty !"
}
return head->item
}
friend std::ostream&operator<<(std::ostream&os, const STACK<T>&stk)
{
for (link t = stk.headt != NULLt = t->next)
{
std::cout <<t->item <<" "
}
return os
}
}
// 中缀表达式转化为后缀表达式，仅支持加减乘除运算、操作数为1位十进制非负整数的表达式。
char* infix2postfix(const char *infix, char *postfix)
{
const size_t N = strlen(infix)
if (N == 0 || postfix == NULL)
{
return postfix
}
stack<char>opcode(N) // 堆栈存放的是操作符
for (size_t i = 0i <Ni++)
{
switch (infix[i])
{
case '(': // 直接忽略左括号
break
case ')': // 弹出操作符
*postfix++ = opcode.pop()
*postfix++ = ' '
break
case '+':
case '-':
case '*':
case '/':
opcode.push(infix[i])// 压入操作符
break
default:
if (isdigit(infix[i])) // 如果是数字，直接输出
{
*postfix++ = infix[i]
*postfix++ = ' '
}
}
}
return postfix
}
// 后缀表达式转化为中缀表达式，仅支持加减乘除运算、操作数为1位十进制非负整数的表达式。
char* postfix2infix(const char *postfix, char *infix)
{
const size_t N = strlen(postfix)
if (N == 0 || infix == NULL)
{
return infix
}
*infix = '\0'// 初始化输出字符串为空串
std::vector<std::string>v
// 初始化，将所有有效字符放入容器
for (size_t i = 0i <Ni++)
{
if (isdigit(postfix[i]) || postfix[i] == '+'
|| postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/')
{
v.push_back(std::string(1, postfix[i]))
}
}
// 处理每一个操作符
for (std::vector<std::string>::iterator b = v.begin()b <v.end()b++)
{
if (*b == "+" || *b == "-" || *b == "*" || *b == "/")
{
copy(v.begin(), v.end(), std::ostream_iterator<std::string>(std::cout, "\n"))
std::cout <<"------------------------------------------------" <<std::endl
std::string opcode = *(b)
std::string oprand1 = *(b - 2)
std::string oprand2 = *(b - 1)
b = v.erase(b - 2, b + 1)// 删除原来的三个表达式，用一个新的表达式替换
b = v.insert(b, std::string("(") + oprand1 + opcode + oprand2 + std::string(")"))
}
}
for (std::vector<std::string>::iterator b = v.begin()b <v.end()b++)
{
strcat(infix, (*b).c_str())
}
return infix
}
// 计算后缀表达式的值，仅支持加减乘除运算、操作数为非负整数的表达式。
int postfix_eval(const char * postfix)
{
const size_t N = strlen(postfix)
if (N == 0)
{
return 0
}
STACK<int>operand(N) // 堆栈存放的是操作数
for (size_t i = 0 i <Ni++)
{
switch (postfix[i])
{
int op1, op2
case '+':
op1 = operand.pop()
op2 = operand.pop()
operand.push(op1 + op2)
break
case '-':
op1 = operand.pop()
op2 = operand.pop()
operand.push(op1 - op2)
break
case '*':
op1 = operand.pop()
op2 = operand.pop()
operand.push(op1 * op2)
break
case '/':
op1 = operand.pop()
op2 = operand.pop()
operand.push(op1 / op2)
break
default:
if (isdigit(postfix[i])) // 执行类似atoi()的功能
{
operand.push(0)
while (isdigit(postfix[i]))
{
operand.push(10 * operand.pop() + postfix[i++] - '0')
}
i--
}
}
std::cout <<operand <<std::endl// 输出堆栈的内容
}
return operand.pop()
}
// 本程序演示了如何后缀表达式和中缀表达式的相互转换，并利用堆栈计算后缀表达式。
// 转换方向：org_infix -->postfix -->infix
int main(int argc, const char *argv[])
{
// const char *org_infix = "(5*(((9+8)*(4*6))+7))"// section 4.3
const char *org_infix = "(5*((9*8)+(7*(4+6))))"// exercise 4.12
std::cout <<"原始中缀表达式：" <<org_infix <<std::endl
char *const postfix = new char[strlen(org_infix) + 1]
infix2postfix(org_infix, postfix)
std::cout <<"后缀表达式：" <<postfix <<std::endl
char *const infix = new char[strlen(postfix) + 1]
postfix2infix(postfix, infix)
std::cout <<"中缀表达式：" <<infix <<std::endl
std::cout <<"计算结果是：" <<postfix_eval(postfix) <<std::endl
std::cout <<"计算结果是：" <<postfix_eval("5 9*8 7 4 6+*2 1 3 * + * + *") <<std::endl// exercise 4.13
delete []infix
delete []postfix
return 0
}
