我正在学习波兰符号,我尝试了一个中缀到后缀转换的程序。
对于 + 和 - 等运算符,我的程序执行得很好。但是对于正确关联的幂运算,它不能正常工作。
例如:表达式 A^B^C 应转换为 ABC^^ ,而我使用的算法将其转换为 AB^C^。
使用的算法是:
Define a stack array.
Scan each character in the infix string
If it is between 0 to 9, append it to postfix string.
If it is left parenthesis push to stack
If it is operator *,+,-,/,%,^ then
If the stack is empty push it to the stack
If the stack is not empty then start a loop:
If the top of the stack has higher precedence
Then pop and append to output string
Else break
Push to the stack
If it is right parenthesis then
While stack not empty and top not equal to left brace
Pop from stack and append to output string
Finally pop out the left brace.
If there is any input in the stack pop and append to the Postfix string.
我应该在算法中进行哪些更改,以便它也适用于右关联运算符。?
我的代码是:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
# define MAX 100
int top=-1;
char infix[100],postfix[100];
char stack[100];
int priority(char symbol)
{
switch(symbol)
{
case '(':return 0;
case '+':
case '-':
return 1;
case '/':
case '*':
case '%':
return 2;
case '^':
return 3;
default :return 0;
}
}
void push(char symbol)
{
if(top==MAX-1)
{
printf("Stack overflow:\n");
exit(1);
}
top=top+1;
stack[top]=symbol;
}
char pop()
{
if(top==-1)
{
printf("Stack underflow:\n");
exit(1);
}
return stack[top--];
}
void infix_to_postfix()
{
int i,p=0;
char symbol,next;
for(i=0;i<strlen(infix);i++)
{
symbol=infix[i];
switch(symbol)
{
case '(':push(symbol);
break;
case ')':while((next=pop())!='(')
{
postfix[p]=next;
p++;
}
break;
case '+':
case '-':
case '*':
case '/':
case '%':
case '^':
while(top!=-1 && priority(stack[top])>=priority(symbol))
{//or stack is empty
postfix[p]=pop();
p++;
}
push(symbol);
break;
default://if operand comes
postfix[p]=symbol;
p++;
}
}
while(top!=-1)
{
postfix[p]=pop();
//printf("%c",pop());
p++;
}
postfix[p]='\0';
}
int main()
{
printf("Enter the infix expression:\n");
scanf("%s",infix);
printf("The post fix expression is:\n");
infix_to_postfix();
printf("-> %s",postfix);
return 0;
}