计算机是如何基于后缀表达式计算的

前一篇文章我们讨论了计算机是如何将中缀表达式转换为后缀表达式的,那么转换后到底计算机是如何计算的呢?本文就来讨论这个主要话题。我们首先来看一下其计算的规则:

【计算规则】

遍历后缀表达式中的数字和符号
	对于数字:进栈
	对于符号:
		从栈中弹出右操作数
		从栈中弹出左操作数
		根据符号进行运算
		将运算结果压入栈中
遍历结束:栈中的唯一数字为计算结果

【代码实现】

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkStack.h"

// 判断是不是数组
int is_number(char ch)
{
	return ch >= '0' && ch <= '9';
}

// 判断是不是操作数
int is_optr(char ch)
{
	return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

// 计算结果
int calc(int left, int right, char optr)
{
	switch (optr)
	{
	case '+':
		return left + right;
	case '-':
		return left - right;
	case '*':
		return left * right;
	case '/':
		return left / right;
	}
	return 0;
}

// 将 ch 数字转换为 int 数字
int value(char ch)
{
	return ch - '0';
}

// 主函数
int compute(const char* code)
{
	// 创建栈
	LinkStack* stack = LinkStack_Create();

	// 用于记录下标
	int i = 0;
	// 用于返回值返回
	int ret = 0;
	// 循环读取每一个字符
	while (code[i])
	{
		// 判断是否是数字
		if (is_number(code[i]))
		{
			// 如果是则压入栈中
			LinkStack_Push(stack, (void*)value(code[i]));
		}
		// 判断是不是操作数
		if (is_optr(code[i]))
		{
			// 如果是取出第一个作为右操作数
			int right = (int)LinkStack_Pop(stack);
			// 再取作为左操作数
			int left = (int)LinkStack_Pop(stack);
			// 根据操作数计算两个数的结果
			int result = calc(left, right, code[i]);
			// 将结果压入栈中
			LinkStack_Push(stack, (void*)result);
		}
		i++;
	}

	// 判断栈中是否只有一个操作数,如果只有一个那证明完成了
	if (LinkStack_Size(stack) == 1)
	{
		// 弹出最后的值给返回值的变量
		ret = (int)LinkStack_Pop(stack);
	}

	// 销毁栈
	LinkStack_Destroy(stack);

	// 返回
	return ret;
}

int main(int argc, char* argv[])
{
	printf("8 + ( 3 - 1 ) * 5 = %d\n", compute("831-5*+"));
	return 0;
}

1 comment

评论