中缀到Postfix转换错误
我正在编写一个基本程序，将中缀表示法中的表达式转换为使用堆栈的后缀表示法。
这是我的程序。
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#define MAX_STACK_SIZE 100
//STACK IMPLEMENTATION BEGINS
struct stack{
int top;
char items[MAX_STACK_SIZE];
};
void push(struct stack* s, char n){
if(s->top==MAX_STACK_SIZE-1)
printf("Stack Overflow. Cannot pushn");
else
s->items[++s->top]=n;
}
bool isempty(struct stack* s){
if(size(s)==0)
return 1;
else return 0;
}
char pop(struct stack* s){
if(isempty(s))
{printf("nStack Underflow. Cannot Popn");
return 0;}
else
{return (s->items[s->top--]);
}
}
bool isfull(struct stack* s){
if(size(s)==MAX_STACK_SIZE)
return 1;
else return 0;
}
void display(struct stack* s){
int num;
if(isempty(s))
printf("Stack empty. Nothing to displayn");
else
{
for(num=0;num<=s->top;num++)
printf("%d ",s->items[num]);
}
}
int size(struct stack* s){
if(s->top==-1)
return 0;
else
return (s->top+1);
}
//STACK IMPLEMENTATION ENDS
//checks if a character entered is an operator or not
bool isOperator(char ch){
if(ch=='-'||ch=='+'||ch=='*'||ch=='/')
return true;
else
return false;
}
//checks if a character entered is an operand(0-9) or not
bool isOperand(char ch){
if(ch>=48 && ch<=57)
return true;
else
return false;
}
//decides the precedence of operators
int precedence(char ch){
if(ch=='*'||ch=='/')
return 2;
if(ch=='+'||ch=='-')
return 1;
}
void main(){
/*
/*Declarations Begin*/
char infix_exp[50],ch;
int a;
struct stack s;
s.top=-1;
/*Declarations End*/
printf("Enter your infix expressionn");
scanf("%s",&infix_exp);
for(a=0;a<strlen(infix_exp);a++)//scanning the entire array
{
if(isOperator(infix_exp[a])){
while(s.top>=0 && isOperator(s.items[s.top]))
{
if(s.items[s.top]=='('|| isempty(&s))
{
push(&s,infix_exp[a]);
}
if(isOperator(s.items[s.top])){
while((s.top--)>=0){
if(precedence(infix_exp[a])>=precedence(s.items[s.top]))
{
ch=pop(&s);
printf("%c",ch);
push(&s,infix_exp[a]);
}
else
{
push(&s,infix_exp[a]);
}}}}}
if(isOperand(infix_exp[a])){printf("%c",infix_exp[a]);}
if(infix_exp[a]=='('){push(&s,'(');}
if(infix_exp[a]==')'){
while(s.top>=0 && s.items[s.top]!='(')
{
ch=pop(&s);
printf("%c",ch);
}
pop(&s);
}}}
这是输出。
Enter your infix expression
6+1
61
RUN FINISHED; exit value 3; real time: 4s; user: 0ms; system: 0ms
我遵循的逻辑是这样的。
用户输入他的表达式后，程序会扫描每个元素。 如果元素是一个操作数，它将被打印。 如果元素是开口支架，则将其推入堆叠。 如果元素是右括号，堆栈中的每个元素都会弹出并打印，直到遇到相应的左括号。 如果元素是一个操作符（由isOperator()函数检查），那么堆栈的顶层元素可以是三个元素之一，
precedence() ）大于或等于堆栈顶部元素的优先级，然后弹出和打印堆栈顶部，并且将中缀表达式元素。 否则，只有中缀表达式元素被推入，没有东西被弹出。 我无法获得输出中的操作员。 什么可能是错误？ 我可能是一个微不足道的人，可能是打印价值观，或者可能是我的逻辑。 任何帮助赞赏。
看起来你正在使用Shunting-yard算法，但是有一些事情你做错了。
首先，算法运行后，您仍然需要打印堆栈的剩余内容并检查不匹配的parens。 正如维基文章所说：
这很容易添加到代码中，只需在for循环后添加如下代码即可：
while(!isempty(&s))
{
ch = pop(&s);
if(ch == ')' || ch == '(') {
printf("nMismatched parensn");
break;
}
printf("%c",ch);
}
但是这并不能立即解决问题，因为还有另一个问题。
第二个问题是当前输入令牌是一个运算符的情况，对此你说：
如果元素是一个操作符（由isOperator（）函数检查），那么堆栈的顶层元素可以是三个元素之一，
这个描述基本上是正确的，除了我认为你的优先级是倒退的，并且你只能在最后一次推送到输出队列（而不是一次堆栈中的每个元素）。
但是你的代码不符合它。
以下是您的代码的相关部分以及注释注释
//if the input token is an operator
if(isOperator(infix_exp[a]))
{
//while s isn't empty and has an operator on top
while(s.top>=0 && isOperator(s.items[s.top]))
{
//if the top element is a '(' (NEVER HAPPENS because '(' isn't an operator)
if(s.items[s.top]=='('|| isempty(&s))
{
push(&s,infix_exp[a]);
}
//If the top element is an operator (ALWAYS HAPPENS)
if(isOperator(s.items[s.top]))
{
//discard the top element of the stack, loop while there are still elements left
while((s.top--)>=0)
{
//if the top element of the stack (after the one that was discarded) has precedence
//then pop it to the output queue and push the input token to the stack
if(precedence(infix_exp[a])>=precedence(s.items[s.top]))
{
ch=pop(&s);
printf("%c",ch);
push(&s,infix_exp[a]);
}
//otherwise push the input token to the stack
else {
push(&s,infix_exp[a]);
}
}
}
}
}
请注意，其中一条if语句从不触发。 你有两个while循环迭代堆栈，其中一个实际上没有做任何迭代。 您在第二个while循环中将堆栈缩小到两个不同的位置。 输入令牌可以被推送输出多次。
总的来说，这只是一个大混乱。
现在我们来看看算法（又是根据维基百科）所说的做法（对于糟糕的格式化，抱歉）：
如果令牌是运算符o1，则：
而在堆栈顶部有一个操作符令牌o2，并且
o1是左联合的，其优先级等于o2的优先级
或者o1的优先级低于o2的优先级，
将o1推入堆栈。
这不符合上述代码，但会怎样？
那么第一部分是正确的
//if the input token is an operator
if(isOperator(infix_exp[a]))
{
然后，您需要使用循环检查来查看堆栈顶部是否存在具有适当优先级的运算符：
//Traverse stack while the precedence is right
while(!isempty(&s) && isOperator(s.items[s.top])
&& (precedence(infix_exp[a]) <= precedence(s.items[s.top])) )
{
并从循环中弹出：
ch = pop(&s);
printf("%c",ch);
}
最后将输入令牌推入堆栈：
push(&s, infix_exp[a]);
}
上一篇: Infix to Postfix conversion error
下一篇: c++