[栈](4.1)前、中、后缀表达式
之前接触的表达式求值的例子，是中缀转后缀运算，对应栈和队列的第21到23题，将在这儿做笔记
21题：中缀表达式转后缀表达式（由字母表示操作数）
思路：
- 初始化两个栈，运算符栈和操作数栈，运算符栈做辅助栈
- 从左到又扫描中缀表达式
- 遇到操作数时，压入操作数栈
遇到运算符时，判断算符栈顶的优先权
- 若栈顶元素小于当前算符，则压入栈中
- 若栈顶元素大于当前算符，则将栈顶元素压入操作数栈中
- 直到达到最右边，将栈中的算符依次压入操作数栈中，输出即可
运算符优先权对照表：
由于用字母代替元素，则两栈都可以用字符类型，完整测试代码如下：
#define STACKSIZE 100
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
char* base;
char* top;
}SqStack;
SqStack S1, S2;
void Push(SqStack* S, char temp);
void Pop(SqStack* S, char* temp);
char Precede(char a, char b);
void InitStack(SqStack* S);
char GetTop(SqStack* S);
void visit();
int main()
{
InitStack(&S1);
InitStack(&S2);
char ch, temp;
ch = getchar();
Push(&S2, '#');
while (GetTop(&S2)!='#' || ch != '#')
{
if (ch >= 'A' && ch <= 'Z')
{
Push(&S1, ch);
ch = getchar();
}
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#')
{
switch (Precede(GetTop(&S2), ch))
{
case'<':
Push(&S2, ch);
ch = getchar();
break;
case'>':
Pop(&S2, &temp);
Push(&S1, temp);
break;
case'=':
Pop(&S2, &temp);
ch = getchar();
break;
}
}
else
{
printf("表达式不合法");
}
}
visit();
system("pause");
return 0;
}
void InitStack(SqStack *S)
{
S->base = (char*)malloc(sizeof(char) * STACKSIZE);
if (S->base == NULL)
{
exit(0);
}
S->top = S->base;
}
void Push(SqStack* S, char temp)
{
*(S->top) = temp;
S->top++;
}
void Pop(SqStack* S, char* temp)
{
S->top--;
*temp = *(S->top);
}
char Precede(char a, char b)//算符优先权比较
{
char op[][7] = { { '>','>','<','<','<','>','>' },
{ '>','>','<','<','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '<','<','<','<','<','=','0' },
{ '>','>','>','>','0','>','>' },
{ '<','<','<','<','<','0','=' }, };
int i, j;
switch (a)
{
case'+':
i = 0;
break;
case'-':
i = 1;
break;
case'*':
i = 2;
break;
case'/':
i = 3;
break;
case'(':
i = 4;
break;
case')':
i = 5;
break;
case'#':
i = 6;
break;
}
switch (b)
{
case'+':
j = 0;
break;
case'-':
j = 1;
break;
case'*':
j = 2;
break;
case'/':
j = 3;
break;
case'(':
j = 4;
break;
case')':
j = 5;
break;
case'#':
j = 6;
break;
}
if (op[i][j] == '0')
{
printf("表达式不合法\n");
exit(-1);
}
return op[i][j];
}
char GetTop(SqStack* S)
{
return *(S->top - 1);
}
void visit()
{
char* p = S1.base;
while (p < S1.top)
{
printf("%c", *p);
p++;
}
}运算结果：
栈顶需要压入#表示开始，输入后加#表示结束
22、对后缀表达式求值
这题跟表达式求值的思路近乎一样，具体可看表达式求值，这里主要考虑输入的是一个后缀表达式，对他进行求值。
后缀表达式没有算符优先权，就从左到右扫描，碰到操作数入操作数栈，碰到算符从操作数栈弹出两个进行运算，结果入栈，直到扫描完毕，将栈顶元素弹出，此时栈应为空，如若不为空，则是操作数过多，表达式不正确，题目给出的单个字母变量可理解为小于十的正整数，则不用链接字符串，如需链接字符串或小数点，则可以看支持浮点数运算的表达式求值，这里只记录前、中、后缀表达式之间的关系
具体测试代码如下所示：
#define STACKSIZE 100
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int* base;
int* top;
}SqStack;
SqStack S1, S2;
void Push(SqStack* S, int temp);
void Pop(SqStack* S, int* temp);
void InitStack(SqStack* S);
void visit();
int main()
{
InitStack(&S1);
char ch;
int a, b;
ch = getchar();
if (ch >= '0' && ch <= '9')
{
Push(&S1, ch-'0');
ch = getchar();
while (ch != '#')
{
if (ch >= '0' && ch <= '9')
{
Push(&S1, ch - '0');
ch = getchar();
}
else if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
{
switch (ch)
{
case'+':
Pop(&S1, &b);
Pop(&S1, &a);
Push(&S1, a + b);
ch = getchar();
break;
case'-':
Pop(&S1, &b);
Pop(&S1, &a);
Push(&S1, a - b);
ch = getchar();
break;
case'*':
Pop(&S1, &b);
Pop(&S1, &a);
Push(&S1, a * b);
ch = getchar();
break;
case'/':
Pop(&S1, &b);
Pop(&S1, &a);
Push(&S1, a / b);
ch = getchar();
break;
}
}
else
{
printf("表达式不正确\n");
break;
}
}
}
else
{
printf("表达式不正确\n");
}
Pop(&S1, &a);
if (S1.top > S1.base)
{
printf("表达式有误\n");
}
else
{
printf("%d", a);
}
system("pause");
}
void InitStack(SqStack *S)
{
S->base = (int*)malloc(sizeof(int) * STACKSIZE);
if (S->base == NULL)
{
exit(0);
}
S->top = S->base;
}
void Push(SqStack* S, int temp)
{
*(S->top) = temp;
S->top++;
}
void Pop(SqStack* S, int* temp)
{
S->top--;
*temp = *(S->top);
}运行结果：
（1+2-3+4）*2
23、判断给定的非空后缀表达式是否为正确的逆波兰式，如果是，将它转换为前缀表达式
依次扫描输入的字符串，碰到操作数则入栈，碰到运算符则取出两个操作数，联接形成子前缀 ，入栈(前后缀规则相同，一个运算符必须匹配两个操作数)，则会出现两种情况：一是运算符过多，二是操作数过多。
当运算符过多的时候，没有足够的操作数来匹配，则在出栈的时候会出错。
当操作数过多的时候，没有足够的运算符来匹配，则匹配完成后栈顶元素不是最后结果。
测试代码如下所示
#define STACK_MAX 100//最大栈空间
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
char* ch;
int length;
}String;//字符串元素
typedef struct
{
String* base;
String* top;
}SqStack;//栈
SqStack S;
void InitStack(SqStack *S)
{
S->base = (String*)malloc(sizeof(String) * STACK_MAX);
S->top = S->base;
}
void Push(SqStack* S, String T)
{
S->top->ch = (char*)malloc(sizeof(char) * T.length + 1);
S->top->length = T.length;
for (int i = 1; i <= T.length; i++)
{
S->top->ch[i] = T.ch[i];
}
S->top++;
}
void Pop(SqStack* S,String *e)
{
if (S->top < S->base)//算符过多
{
printf("表达式错误\n");
system("pause");
exit(0);
}
S->top--;
e->ch = (char*)malloc(sizeof(char) * (S->top->length + 1));
e->length = S->top->length;
for (int i = 1; i <= S->top->length; i++)
{
e->ch[i] = S->top->ch[i];
}
}
void Concat(String S, String T, String* C)
{
if (S.length <= 0 || T.length <= 0)
{
printf("表达式错误\n");//算符过多
system("pause");
exit(0);
}
C->ch = (char*)malloc(sizeof(char) * (S.length + T.length + 1));
C->length = S.length + T.length;
int i;
for (i = 1; i <= S.length; i++)
{
C->ch[i] = S.ch[i];
}
for (int j = 1; i <= C->length; j++, i++)
{
C->ch[i] = T.ch[j];
}
}
int main()
{
InitStack(&S);
String s, p, a, temp, p1;
temp.ch = (char*)malloc(sizeof(char) * 5);
char ch;
ch = getchar();
while (ch != '#')
{
if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
{
temp.length = 1;
temp.ch[1] = ch;
Pop(&S, &s);
Pop(&S, &a);
Concat(temp, a, &p);
Concat(p, s, &p1);
Push(&S, p1);
}
else
{
temp.length = 1;
temp.ch[1] = ch;
Push(&S, temp);
}
ch = getchar();
}
Pop(&S, &temp);
if (S.top > S.base)//操作数过多
{
printf("表达式不正确");
}
else
{
for (int i = 1; i <= temp.length; i++)
{
printf("%c", temp.ch[i]);
}
}
system("pause");
return 0;
}运行结果：
再次声明，后缀表达式没有优先权，别绕进去了，直接遇到算符提出来放两个操作数前面就好！！只有中缀转前缀才需要考虑优先权！！