【算法练习五】逆波兰表达式

逆波兰表达式又叫后缀表达式,中学时候学的那种表达式叫中缀表达式。

例如,5×(6+3)÷3-1      ,  3×(4÷(2+1)×2)-3

例子中的这两个式子,就是中缀表达式。下面这两个就是后缀表达式:

563+×3÷1-      ,    3421+÷2××3-

中缀表达式变后缀表达式方法:

见到数字直接输出,见到符号按一定规则入栈出栈。

规则就是,用当前的符号与栈顶的符号比较优先级,如果当前符号优先级小于栈顶符号的优先级,则把栈里面的符号都弹出来。括号的操作除外,括号是左括号优先级最高,不管跟啥比,都是入栈;右括号是优先级最低,跟啥比都是弹出栈内符号,但只弹到跟它匹配的最近的那个左括号。

这里就涉及到一个符号优先级的问题。看下图吧,从上往下的符号是优先级从高到低。

这样就可以开始说怎么互相转换了。上面的两个例子式子都说一说:

                       5×(6+3)÷3-1

先看到的是5,直接输出,现在的后缀表达式为:“5”。下一个,“×”,压入栈中。下一个,“(”,优先级超级高,处在金字塔顶端的符号,也压入栈中。下一个,“6”,数字,直接输出,现在的后缀表达式为:“56”。目前状况看下图吧。

下一个, “+” ,当栈顶是 “(” 的时候,当前的符号优先级是一定小于 “(” 的,但不能还按照原来的规则,把栈内符号弹出。 “(” 的弹出条件是等到与之匹配的最近的 “)” 。只有等到了 “)” , “(” 才弹出。当然了, “(” 和 “)” 中间一定还会有别的运算符,弹的时候一起都弹出来。而且当遇到 “)” 的时候,不是全栈都弹出来,而是弹到 “(” 停止。那么,再说回来,当前符号是 “+” ,由于 “(” 只等到 “)” 才弹出,所以把 “+” 压入栈中。下一个, “3” ,直接输出。目前的状况看下图。

下一个, “)” ,这个优先级极低,所以弹出栈中元素,但这个也不能按常规的规则操作。遇到 “)” 了,不应把全栈都弹出来,而是只弹到 “(” ,因此,现在栈里面从栈顶一直往下弹,弹到 “(” 为止。目前的状况看下图。

下一个, “÷” ,跟栈顶符号 “×” 比优先级为同级,则将栈中元素都弹出来,即 “×” 弹出,将 “÷” 压入栈中。因为转换规则是,当前符号与栈顶符号比较,优先级大于栈顶符号,才不弹出直接压入;否则就要先弹出,即清空栈再压入。

简单说就是,当前符号优先级大于栈顶符号优先级时,不弹出直接压入;小于等于时,弹出再压入。目前的状况看下图。

下一个, “3” ,直接输出,此时输出为:563+×3。下一个, “-” ,这个符号跟栈顶符号比较,优先级低于栈顶符号,so,弹出栈中元素,把 “-” 压入栈中。目前的状况看下图。

下一个, “1” ,直接输出,此时输出为:563+×3÷1。原中值表达式没有元素了,最后一步操作将栈内还没弹出的符号都弹出。【在计算机中,其实是自动向中缀表达式末尾填充一个 “#” ,由于 “#” 优先级最低,这样在搜索到 “#” 时,就会清空栈。但 “#” 不参与表达式的计算,就是输出时,没有 “#” 。这和数组最后一位是结束符是同样的道理。】弹出时符号写在输出中的顺序是,按从栈底到栈顶这个顺序在输出表达式中从左到右列出。最后的输出就是:563+×3÷1-

下面贴一张百度百科的算法说明

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OK 1
#define ERROR 0
const int maxn = 20;

typedef struct Stack{
int max_size, top_index;
char *elements;
}Stack;

void init(Stack *s, int size){
s->max_size = size;
s->top_index = -1;
s->elements = (char*)malloc(sizeof(char)*size);
}

int push(Stack *s, char value){
if (s->top_index >= s->max_size – 1){
return ERROR;
}
s->top_index++;
s->elements[s->top_index]=value;
return OK;
}

void pop(Stack *s){
if (s->top_index <0){
return;
}
s->top_index–;
}

int top(Stack *s){
return s->elements[s->top_index];
}

void clear(Stack *s){
free(s->elements);
free(s);
}

int isOperator(char c){
return (c == ‘+’ || c == ‘-‘ || c == ‘*’ || c == ‘/’);
}

int priority(char c){
if (c == ‘*’ || c == ‘/’){
return 2;
}
if (c == ‘+’ || c == ‘-‘){
return 1;
}
else{
return 0;
}
}

int op(int a, int b, char c){
int res;
if (c == ‘+’){
res = a + b;
}
else if (c == ‘-‘){
res = a – b;
}
else if (c == ‘*’){
res = a*b;
}
else if (c == ‘/’){
res = a / b;
}
return res;
}

int main(){
char s[maxn];
scanf(“%s”, &s);
int n = strlen(s);
Stack *stack = (Stack*)malloc(sizeof(Stack));
init(stack, n);
char change[maxn];
int outlen = 0;
memset(change, ‘\0’, maxn);
memset(stack->elements, ‘\0’, n);
for (int i = 0; i<n; i++){
if (s[i] >= ‘0’&&s[i] <= ‘9’){
change[outlen++] = s[i];
}
while (isOperator(s[i])){
if (stack->top_index == -1 || priority(s[i])>priority(top(stack))){
push(stack,s[i]);
break;
}
else{
change[outlen++] = top(stack);
pop(stack);
}
}
}
while (stack->top_index != -1){
change[outlen++] = top(stack);
pop(stack);
}
for (int i = 0; i < sizeof(change); i++){
if (change[i] >= ‘0’&&change[i] <= ‘9’){
push(stack, change[i]);
}
else if (isOperator(change[i])){
char c = change[i];
int b = top(stack)-‘0’;
pop(stack);
int a = top(stack)-‘0′;
pop(stack);
push(stack, op(a, b, c)+’0’);
}
}
printf(“%s”,change);
printf(“\n%d”, top(stack)-‘0’);
clear(stack);
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注