#include <stdio.h>
#include <stdlib.h> /* for atof() */
#define MAXOP 100 /* max size of operand or operator */
#define NUMBER '0' /* signal that a number was found */
int getOp(char [])
void push(double)
double pop(void)
main() {
int type
double op2
char s[MAXOP]
while ((type = getOp(s)) != EOF) {
switch (type) {
case NUMBER:
push(atof(s))
break
case '+':
push(pop() + pop())
break
case '*':
push(pop() * pop())
break
case '-':
op2 = pop()
push(pop() - op2)
break
case '/':
op2 = pop()
if (op2 != 0.0)
push(pop() / op2)
else
puts("error: zero divisor\n")
break
case '\n':
printf("\t%.8g\n", pop())
break
default:
printf("error: unknown command %s\n", s)
break
}
}
return 0
}
/*************************************************************************
Definition of push() and pop().
*************************************************************************/
#define MAXVAL 100 /* maximum depth of val stack */
int sp = 0 /* next free stack position */
double val[MAXVAL] /* value stack */
/* push: push f onto value stack */
void push(double f) {
if (sp <MAXVAL)
val[sp++] = f
else
printf("error: stack full, can't push %g\n", f)
}
/* pop: pop and return top value from stack */
double pop(void) {
if (sp >0)
return val[--sp]
else {
puts("error: stack empty\n")
return 0.0
}
}
/*************************************************************************
Definition of getOp().
*************************************************************************/
#include <ctype.h>
int getChar_localVersion(void)
void ungetChar_localVersion(int c)
/* getOp: get next character or numeric operand */
int getOp(char s[]) {
int i, c
while ((s[0] = c = getChar_localVersion()) == ' ' || c == '\t')
s[1] = '\0'
if (!isdigit(c) &&c != '.' &&c != '-')
return c /* not a number */
i = 0
if (c == '-') /* is valid sign if followed by a digit */
if(isdigit(s[1] = c = getChar_localVersion()))
++i
else {
ungetChar_localVersion(c)
s[1] = '\0'
return s[0]
}
if (isdigit(c)) /* collect integer part */
while (isdigit(s[++i] = c = getChar_localVersion()))
if (c == '.') /* collect fraction part */
while (isdigit(s[++i] = c = getChar_localVersion()))
s[i] = '\0'
if (c != EOF)
ungetChar_localVersion(c)
return NUMBER
}
/*************************************************************************
Definition of getChar_localVersion() and ungetChar_localVersion().
*************************************************************************/
#define BUFSIZE 100
char buf[BUFSIZE] /* buffer for ungetChar_localVersion */
int bufp = 0 /* next free position in buf */
/* getChar_localVersion: get a (possibly pushed-back) character */
int getChar_localVersion(void) {
return (bufp >0) ? buf[--bufp] : getchar()
}
/* ungetChar_localVersion: push character back on input */
void ungetChar_localVersion(int c) {
if (bufp >= BUFSIZE)
puts("ungetChar_localVersion: too many characters\n")
else
buf[bufp++] = c
}
你可以扩展一下。// 中缀表达式转化为后缀表达式，仅支持加减乘除运算、 *** 作数为1位十进制非负整数的表达式。
char* infix2postfix(const char *infix, char *postfix)
{
const size_t N = strlen(infix)
if (N == 0 || postfix == NULL)
{
return postfix
}
stack<char>opcode(N) // 堆栈存放的是 *** 作符
for (size_t i = 0i <Ni++)
{
switch (infix[i])
{
case '(': // 直接忽略左括号
break
case ')': // d出 *** 作符
*postfix++ = opcode.pop()
*postfix++ = ' '
break
case '+':
case '-':
case '*':
case '/':
opcode.push(infix[i])// 压入 *** 作符
break
default:
if (isdigit(infix[i])) // 如果是数字，直接输出
{
*postfix++ = infix[i]
*postfix++ = ' '
}
}
}
return postfix
}
中缀表达式如1*2+(2-1), 其运算符一般出现在 *** 作数之间, 因此称为中缀表达式,也就是大家编程中写的表达式。编译系统不考虑表达式的优先级别, 只是对表达式从左到右进行扫描, 当遇到运算符时, 就把其前面的两个 *** 作数取出, 进行 *** 作。为达到上述目的, 就要将中缀表达式进行改写,变为后缀表达式 如上面的表达式1*2+(2-1), 就变为12*21-+
后缀表达式中不含有括号, 且后缀表达式的 *** 作数和中缀表达式的 *** 作数排列次序完全相同, 只是运算符的次序发生了改变。我们实现的时候，只需要用一个特定工作方式的数据结构（栈），就可以实现。
其中stack op用来存放运算符栈。数组ans用来存放后缀表达式。
算法思想：
从左到右扫描中缀表达式，是 *** 作数就放进数组ans的末尾。
如果是运算符的话，分为下面3种情况：
1）如果是‘（’直接压入op栈。
2）如果是‘）’，依次从op栈d出运算符加到数组ans的末尾，知道遇到'（'；
3) 如果是非括号，比较扫描到的运算符，和op栈顶的运算符。如果扫描到的运算符优先级高于栈顶运算符
则，把运算符压入栈。否则的话，就依次把栈中运算符d出加到数组ans的末尾，直到遇到优先级低于扫描
到的运算符，并且把扫描到的运算符压入栈中。
就这样依次扫描，知道结束为止。
如果扫描结束，栈中还有元素，则依次d出加到数组ans的末尾，就得到了后缀表达式。
我空间里面有详细介绍，中缀转换后缀的代码和问题描述，主要是理解算法的思想，和数据结构，这样才算掌握了。
http://hi.baidu.com/huifeng00/blog/item/70cb280dabd9d4216059f3d1.html
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）