c - 如何实现我的后缀算法的数学POW - C

Question

我有在 C 中创建后缀的简单算法。

这是一个sample program我添加了处理 pow 的内容:

/***********************************************************
* You can use all the programs on  www.c-program-example.com
* for personal and learning purposes. For permissions to use the
* programs for commercial purposes,
* contact info@c-program-example.com
* To find more C programs, do visit www.c-program-example.com
* and browse!
* 
*                                  Happy Coding
***********************************************************/

#define SIZE 50            /* Size of Stack */
#include <ctype.h>
char s[SIZE];
int top = -1; /* Global declarations */

push(char elem) { /* Function for PUSH operation */
 s[++top] = elem;
}

char pop() { /* Function for POP operation */
 return (s[top--]);
}

int pr(char elem) { /* Function for precedence */
 switch (elem) {
 case '#':
  return 0;
 case '(':
  return 1;
 case '+':
 case '-':
  return 2;
 case '*':
 case '/':
  return 3;
 case '^':
  return 4;
 }
}

main() { /* Main Program */
 char infx[50], pofx[50], ch, elem;
 int i = 0, k = 0;
 printf("\n\nRead the Infix Expression ? ");
 scanf("%s", infx);
 push('#');
 while ((ch = infx[i++]) != '\0') {
  if (ch == '(')
   push(ch);
  else if (isalnum(ch))
   pofx[k++] = ch;
  else if (ch == ')') {
   while (s[top] != '(')
    pofx[k++] = pop();
   elem = pop(); /* Remove ( */
  } else { /* Operator */
   while (pr(s[top]) >= pr(ch))
    pofx[k++] = pop();
   push(ch);
  }
 }
 while (s[top] != '#') /* Pop from stack till empty */
  pofx[k++] = pop();
 pofx[k] = '\0'; /* Make pofx as valid string */
 printf("\n\nGiven Infix Expn: %s  Postfix Expn: %s\n", infx, pofx);
}

我尝试实现 math pow，但它不起作用，你能帮助我吗？我该如何实现？例如输入是:(1-5)^2^3，输出是15-2^3^但是这是错误的，正确的输出是 15-23^^

我认为该错误出现在方法 int pr(char elem) 中，您能帮助我更多吗？

Answer 1

问题不在于 int pr(char elem)，因为它是一个非常简单的函数，仅返回运算符的优先级值。它比这更微妙:

数字(实际上还有字母字符)立即被“推送”到pofx中。括号和运算符需要临时保存在自己的堆栈中:s。仅在字符串末尾，或者遇到更高优先级运算符时，当前位于其自己堆栈上的运算符需要添加到pofx:

./infix "(1-5)+2*3"
pushing number '1'
pushing operator '-' (top is ()
pushing number '5'
resolving parentheses
pushing operator '+' (top is #)
pushing number '2'
pushing operator '*' (top is +)
pushing number '3'
Postfix Expn: 15-23*+

原始代码检查“更高或等于”优先级:

.. /* Operator */
   while (pr(s[top]) >= pr(ch))

给定..^2^3部分，推送的顺序是

^ - operator, #4 -> push on operand stack
2 - digit -> push immediately
^ - operator, #4 -> operand stack is '^' which is *equal*, so move to output stack
    and push next operand
3 - digit -> push immediately
.. end of input, move operand stack ('^' only) to end of output

如果您将比较更改为此，它将正确工作:

while (pr(s[top]) > pr(ch))